Re: [Google/4_8] Reduce memory overhead of LIPO COMDAT fixups

[Rong Xu <xur at google dot com>]

This patch looks good to me.

-Rong

On Thu, Jun 5, 2014 at 12:45 PM, Teresa Johnson <tejohnson@google.com> wrote:
> (cc'ing a few additional people to help with review as David is out
> and I'm not sure Rong is available)
>
> This patch greatly reduces the memory overhead of the new COMDAT fixup
> analysis, by changing the second level hash tables to linked lists.
> I found that almost none of the second level hash tables contained more
> than one entry, but each hash table required a lot of memory overhead.
>
> I also now query the fixup type before adding the checksums to the
> pointer sets during callgraph building, which would have enabled a workaround
> for the memory issue.
>
> Tested with regression tests and internal tests (see ref below for details).
>
> Google ref b/15415042.
>
> 2014-06-05  Teresa Johnson  <tejohnson@google.com>
>
>         * dyn-ipa.c (struct lineno_checksum_alias): Replaced pointer set.
>         (struct checksum_alias_info): Enabled linked list.
>         (cfg_checksum_get_key): Removed.
>         (find_cfg_checksum): New function.
>         (cfg_checksum_insert): Operate on linked list.
>         (checksum_set_insert): Ditto.
>         (gcov_build_callgraph): Allow disabling checksum insertion.
>         (gcov_find_new_ic_target): Operate on linked list.
>         (gcov_fixup_counters_checksum): Ditto.
>         (gcov_fixup_counters_lineno): Ditto.
>         (__gcov_compute_module_groups): Compute fixup type earlier.
>
> Index: dyn-ipa.c
> ===================================================================
> --- dyn-ipa.c   (revision 211288)
> +++ dyn-ipa.c   (working copy)
> @@ -79,16 +79,15 @@ struct dyn_cgraph
>    unsigned num_nodes_executed;
>    /* used by new algorithm  */
>    struct modu_node *modu_nodes;
> -  /* Set indexed by lineno_checksum, returns another dyn_pointer_set*,
> -     indexed by cfg_checksum.  That returns a checksum_alias_info struct.  */
> +  /* Set indexed by lineno_checksum, returns a linked list of
> +     checksum_alias_info structs.  */
>    struct dyn_pointer_set *lineno_pointer_sets;
>  };
>
>  /* Struct holding information for functions with the same lineno_checksum.  */
>  struct lineno_checksum_alias
>  {
> -  /* Set indexed by cfg_checksum, holding a checksum_alias_info struct.  */
> -  struct dyn_pointer_set *cfg_pointer_set;
> +  struct checksum_alias_info *cfg_checksum_list;
>    unsigned lineno_checksum;
>  };
>
> @@ -96,6 +95,7 @@ struct lineno_checksum_alias
>     checksums.  */
>  struct checksum_alias_info
>  {
> +  struct checksum_alias_info *next_cfg_checksum;
>    struct checksum_alias *alias_list;
>    unsigned cfg_checksum;
>  };
> @@ -205,6 +205,7 @@ pointer_set_create (unsigned (*get_key) (const voi
>  static struct dyn_cgraph the_dyn_call_graph;
>  static int total_zero_count = 0;
>  static int total_insane_count = 0;
> +static int fixup_type = 0;
>
>  enum GROUPING_ALGORITHM
>  {
> @@ -374,14 +375,6 @@ lineno_checksum_get_key (const void *p)
>    return ((const struct lineno_checksum_alias *) p)->lineno_checksum;
>  }
>
> -/* The cfg_checksum value in P is the key for a cfg_pointer_set.  */
> -
> -static inline unsigned
> -cfg_checksum_get_key (const void *p)
> -{
> -  return ((const struct checksum_alias_info *) p)->cfg_checksum;
> -}
> -
>  /* Create a new checksum_alias struct for function with GUID, FI_PTR,
>     and ZERO_COUNTS flag.  Prepends to list NEXT and returns new struct.  */
>
> @@ -398,28 +391,44 @@ new_checksum_alias (gcov_type guid, const struct g
>    return alias;
>  }
>
> -/* Insert a new checksum_alias struct into pointer set P for function with
> +/* Locate the checksum_alias_info in LIST that matches CFG_CHECKSUM.  */
> +
> +static struct checksum_alias_info *
> +find_cfg_checksum (struct checksum_alias_info *list, unsigned cfg_checksum)
> +{
> +  for (; list; list = list->next_cfg_checksum)
> +    {
> +      if (list->cfg_checksum == cfg_checksum)
> +        return list;
> +    }
> +  return NULL;
> +}
> +
> +/* Insert a new checksum_alias struct into LIST for function with
>     CFG_CHECKSUM and associated GUID, FI_PTR, and ZERO_COUNTS flag.  */
>
> -static void
> -cfg_checksum_set_insert (struct dyn_pointer_set *p, unsigned cfg_checksum,
> -                         gcov_type guid, const struct gcov_fn_info *fi_ptr,
> -                         int zero_counts)
> +static struct checksum_alias_info *
> +cfg_checksum_insert (unsigned cfg_checksum, gcov_type guid,
> +                     const struct gcov_fn_info *fi_ptr, int zero_counts,
> +                     struct checksum_alias_info *list)
>  {
> -  struct checksum_alias_info **m = (struct checksum_alias_info **)
> -    pointer_set_find_or_insert (p, cfg_checksum);
> -  if (*m)
> +  struct checksum_alias_info *alias_info;
> +  alias_info = find_cfg_checksum (list, cfg_checksum);
> +  if (alias_info)
>      {
> -      gcc_assert ((*m)->alias_list);
> -      (*m)->alias_list = new_checksum_alias (guid, fi_ptr, zero_counts,
> -                                             (*m)->alias_list);
> +      gcc_assert (alias_info->alias_list);
> +      alias_info->alias_list = new_checksum_alias (guid, fi_ptr, zero_counts,
> +                                                   alias_info->alias_list);
> +      return list;
>      }
>    else
>      {
> -      *m = XNEW (struct checksum_alias_info);
> -      (*m)->cfg_checksum = cfg_checksum;
> -      (*m)->alias_list = new_checksum_alias (guid, fi_ptr, zero_counts, NULL);
> -      p->n_elements++;
> +      alias_info = XNEW (struct checksum_alias_info);
> +      alias_info->next_cfg_checksum = list;
> +      alias_info->cfg_checksum = cfg_checksum;
> +      alias_info->alias_list = new_checksum_alias (guid, fi_ptr, zero_counts,
> +                                                   NULL);
> +      return alias_info;
>      }
>  }
>
> @@ -440,16 +449,16 @@ checksum_set_insert (unsigned lineno_checksum, uns
>      pointer_set_find_or_insert (p, lineno_checksum);
>    if (*m)
>      {
> -      cfg_checksum_set_insert ((*m)->cfg_pointer_set, cfg_checksum, guid,
> -                               fi_ptr, zero_counts);
> +      (*m)->cfg_checksum_list = cfg_checksum_insert (cfg_checksum, guid,
> +                                                     fi_ptr, zero_counts,
> +                                                     (*m)->cfg_checksum_list);
>      }
>    else
>      {
>        *m = XNEW (struct lineno_checksum_alias);
>        (*m)->lineno_checksum = lineno_checksum;
> -      (*m)->cfg_pointer_set = pointer_set_create (cfg_checksum_get_key);
> -      cfg_checksum_set_insert ((*m)->cfg_pointer_set, cfg_checksum, guid,
> -                               fi_ptr, zero_counts);
> +      (*m)->cfg_checksum_list = cfg_checksum_insert (cfg_checksum, guid,
> +                                                     fi_ptr,
> zero_counts, NULL);
>        p->n_elements++;
>      }
>  }
> @@ -844,9 +853,10 @@ gcov_build_callgraph (void)
>                      total_arc_count += ci_ptr->values[arc];
>                    if (total_arc_count != 0)
>                      the_dyn_call_graph.num_nodes_executed++;
> -                  checksum_set_insert (fi_ptr->lineno_checksum,
> -                                       fi_ptr->cfg_checksum, caller->guid,
> -                                       fi_ptr, total_arc_count == 0);
> +                  if (fixup_type)
> +                    checksum_set_insert (fi_ptr->lineno_checksum,
> +                                         fi_ptr->cfg_checksum, caller->guid,
> +                                         fi_ptr, total_arc_count == 0);
>                  }
>                ci_ptr++;
>              }
> @@ -2454,10 +2464,10 @@ gcov_find_new_ic_target (gcov_type caller_guid, gc
>    struct lineno_checksum_alias **line_alias = (struct lineno_checksum_alias **)
>      pointer_set_find_or_insert (p, callee_fi_ptr->lineno_checksum);
>    gcc_assert (*line_alias);
> -  struct checksum_alias_info **cfg_alias = (struct checksum_alias_info **)
> -    pointer_set_find_or_insert ((*line_alias)->cfg_pointer_set,
> -                                callee_fi_ptr->cfg_checksum);
> -  gcc_assert (*cfg_alias);
> +  struct checksum_alias_info *cfg_alias
> +      = find_cfg_checksum ((*line_alias)->cfg_checksum_list,
> +                           callee_fi_ptr->cfg_checksum);
> +  gcc_assert (cfg_alias);
>
>
>    /* Scan the list of checksum aliases for one that is located in caller's
> @@ -2465,7 +2475,7 @@ gcov_find_new_ic_target (gcov_type caller_guid, gc
>    gcov_type new_guid = 0;
>    unsigned caller_mod_id = get_module_ident_from_func_glob_uid (caller_guid);
>    struct checksum_alias *alias;
> -  for (alias = (*cfg_alias)->alias_list; alias;
> +  for (alias = cfg_alias->alias_list; alias;
>         alias = alias->next_alias)
>      {
>        if (get_module_ident_from_func_glob_uid (alias->guid)
> @@ -2901,24 +2911,18 @@ merge_ctrs (struct gcov_ctr_info *dest_ctrs,
>  }
>
>  /* Walks the set of functions that have the same lineno and cfg checksum, and
> -   performs counter merging.  VALUE contains the checksum_alias_info structure
> -   for a given lineno and cfg checksum combination, and DATA1
> contains a pointer
> +   performs counter merging.  INFO contains the checksum_alias_info structure
> +   for a given lineno and cfg checksum combination. CHANGED points
>     to a flag that should be set to 1 if any fixups were applied.  */
>
>  static int
> -gcov_fixup_counters_checksum (const void *value,
> -                              void *data1,
> -                              void *data2 ATTRIBUTE_UNUSED,
> -                              void *data3 ATTRIBUTE_UNUSED)
> +gcov_fixup_counters_checksum (const struct checksum_alias_info *info,
> +                              int *changed)
>  {
> -  const struct checksum_alias_info *a
> -      = (const struct checksum_alias_info*) value;
> -  int *changed = (int *) data1;
> -
>    /* See if there are any zero count functions to fix.  */
>    int found = 0;
>    struct checksum_alias *alias;
> -  for (alias = a->alias_list; alias;
> +  for (alias = info->alias_list; alias;
>         alias = alias->next_alias)
>      {
>        if (alias->zero_counts)
> @@ -2933,7 +2937,7 @@ static int
>    /* Walk the aliases and merge the non-zero counters into a dummy copy.  */
>    struct gcov_ctr_info *merged_ctrs = init_merged_ctrs ();
>    found = 0;
> -  for (alias = a->alias_list; alias;
> +  for (alias = info->alias_list; alias;
>         alias = alias->next_alias)
>      {
>        if (alias->zero_counts)
> @@ -2951,7 +2955,7 @@ static int
>    *changed = 1;
>
>    /* Walk them again and copy the merged counters into 0-count copies.  */
> -  for (alias = a->alias_list; alias;
> +  for (alias = info->alias_list; alias;
>         alias = alias->next_alias)
>      {
>        if (!alias->zero_counts)
> @@ -2977,9 +2981,11 @@ gcov_fixup_counters_lineno (const void *value,
>    const struct lineno_checksum_alias *a
>        = (const struct lineno_checksum_alias*) value;
>    int *changed = (int *) data1;
> -  pointer_set_traverse (a->cfg_pointer_set,
> -                        gcov_fixup_counters_checksum,
> -                        changed, 0, 0);
> +  struct checksum_alias_info *cfg_alias_list = a->cfg_checksum_list;
> +  for (; cfg_alias_list; cfg_alias_list = cfg_alias_list->next_cfg_checksum)
> +    {
> +      gcov_fixup_counters_checksum (cfg_alias_list, changed);
> +    }
>    return 1;
>  }
>
> @@ -3046,6 +3052,12 @@ __gcov_compute_module_groups (void)
>        return 0;
>      }
>
> +  const char *do_fixup = 0;
> +  fixup_type = __gcov_lipo_comdat_algorithm;
> +  do_fixup = getenv ("GCOV_DYN_DO_FIXUP");
> +  if (do_fixup)
> +    fixup_type = atoi (do_fixup);
> +
>    /* First compute dynamic call graph.  */
>    gcov_build_callgraph ();
>
> @@ -3055,12 +3067,6 @@ __gcov_compute_module_groups (void)
>
>    gcov_dump_callgraph (cut_off_count);
>
> -  const char *do_fixup = 0;
> -  int fixup_type = __gcov_lipo_comdat_algorithm;
> -  do_fixup = getenv ("GCOV_DYN_DO_FIXUP");
> -  if (do_fixup)
> -    fixup_type = atoi (do_fixup);
> -
>    int changed = 0;
>    if (fixup_type & 0x2)
>      changed |= gcov_fixup_zero_counters ();
>
>
> --
> Teresa Johnson | Software Engineer | tejohnson@google.com | 408-460-2413