| Message ID | CAAe5K+X3Rt4GTi8bsYwQJpmo-jGbHMmdXZe5p1Y447eZVSj+ag@mail.gmail.com |
|---|---|
| State | New |
| Headers | show |
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
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++; }
(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. } @@ -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 ();