/* Compile this one with gcc. */ /* Copyright (C) 2009. Free Software Foundation, Inc. Contributed by Xinliang David Li (davidxl@google.com) and Raksit Ashok (raksit@google.com) This file is part of GCC. GCC is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 3, or (at your option) any later version. GCC is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. Under Section 7 of GPL version 3, you are granted additional permissions described in the GCC Runtime Library Exception, version 3.1, as published by the Free Software Foundation. You should have received a copy of the GNU General Public License and a copy of the GCC Runtime Library Exception along with this program; see the files COPYING3 and COPYING.RUNTIME respectively. If not, see . */ #include "libgcov.h" struct dyn_pointer_set; #ifndef IN_GCOV_TOOL #define XNEWVEC(type,ne) (type *)malloc(sizeof(type) * (ne)) #define XCNEWVEC(type,ne) (type *)calloc(1, sizeof(type) * (ne)) #define XNEW(type) (type *)malloc(sizeof(type)) #define XDELETEVEC(p) free(p) #define XDELETE(p) free(p) #endif struct dyn_cgraph_node { struct dyn_cgraph_edge *callees; struct dyn_cgraph_edge *callers; struct dyn_pointer_set *imported_modules; gcov_type guid; gcov_type sum_in_count; gcov_unsigned_t visited; }; struct dyn_cgraph_edge { struct dyn_cgraph_node *caller; struct dyn_cgraph_node *callee; struct dyn_cgraph_edge *next_caller; struct dyn_cgraph_edge *next_callee; gcov_type count; int indirect; }; struct dyn_module_info { struct dyn_pointer_set *imported_modules; gcov_unsigned_t max_func_ident; /* Used by new algorithm. This dyn_pointer_set only stored the gcov_info pointer, keyed by module ident. */ struct dyn_pointer_set *exported_to; gcov_unsigned_t group_ggc_mem; }; struct dyn_cgraph { struct dyn_pointer_set **call_graph_nodes; struct gcov_info **modules; /* supplement module information */ struct dyn_module_info *sup_modules; unsigned num_modules; unsigned num_nodes_executed; /* used by new algorithm */ struct modu_node *modu_nodes; /* 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 { struct checksum_alias_info *cfg_checksum_list; unsigned lineno_checksum; }; /* Struct holding information about functions with the same lineno and cfg checksums. */ struct checksum_alias_info { struct checksum_alias_info *next_cfg_checksum; struct checksum_alias *alias_list; unsigned cfg_checksum; }; /* Implements list of guid and corresponding fi_ptr for functions with matching checksums. */ struct checksum_alias { struct checksum_alias *next_alias; gcov_type guid; const struct gcov_fn_info *fi_ptr; /* Non-NULL pointer to flag if this function has all-zero arc counts, to be set if we perform fixup. */ char *zero_count_fixup; }; /* Module info is stored in dyn_caph->sup_modules which is indexed by m_ix. */ struct modu_node { struct gcov_info *module; struct modu_edge *callees; struct modu_edge *callers; }; struct modu_edge { struct modu_node *caller; struct modu_node *callee; struct modu_edge *next_caller; struct modu_edge *next_callee; unsigned n_edges; /* used when combining edges */ gcov_type sum_count; unsigned char visited; }; struct dyn_pointer_set { size_t log_slots; size_t n_slots; /* n_slots = 2^log_slots */ size_t n_elements; void **slots; unsigned (*get_key) (const void *); }; typedef long dyn_fibheapkey_t; typedef struct dyn_fibheap { size_t nodes; struct fibnode *min; struct fibnode *root; } *dyn_fibheap_t; typedef struct fibnode { struct fibnode *parent; struct fibnode *child; struct fibnode *left; struct fibnode *right; dyn_fibheapkey_t key; void *data; unsigned int degree : 31; unsigned int mark : 1; } *fibnode_t; static dyn_fibheap_t dyn_fibheap_new (void); static fibnode_t dyn_fibheap_insert (dyn_fibheap_t, dyn_fibheapkey_t, void *); static void *dyn_fibheap_extract_min (dyn_fibheap_t); extern gcov_unsigned_t __gcov_lipo_cutoff; extern gcov_unsigned_t __gcov_lipo_random_seed; extern gcov_unsigned_t __gcov_lipo_random_group_size; extern gcov_unsigned_t __gcov_lipo_propagate_scale; extern gcov_unsigned_t __gcov_lipo_dump_cgraph; extern gcov_unsigned_t __gcov_lipo_max_mem; extern gcov_unsigned_t __gcov_lipo_comdat_algorithm; extern gcov_unsigned_t __gcov_lipo_grouping_algorithm; extern gcov_unsigned_t __gcov_lipo_merge_modu_edges; extern gcov_unsigned_t __gcov_lipo_weak_inclusion; #if defined(inhibit_libc) void __gcov_build_callgraph (char **zero_counts) {} #else int __gcov_compute_module_groups (char **zero_counts) ATTRIBUTE_HIDDEN; void __gcov_finalize_dyn_callgraph (void) ATTRIBUTE_HIDDEN; static void gcov_dump_callgraph (gcov_type); static void gcov_dump_cgraph_node_short (struct dyn_cgraph_node *node); static void gcov_dump_cgraph_node (struct dyn_cgraph_node *node, unsigned m, unsigned f); static int do_cgraph_dump (void); static void gcov_dump_cgraph_node_dot (struct dyn_cgraph_node *node, unsigned m, unsigned f, gcov_type cutoff_count); static void pointer_set_destroy (struct dyn_pointer_set *pset); static void pointer_set_destroy_not_free_value_pointer (struct dyn_pointer_set *); static void ** pointer_set_find_or_insert (struct dyn_pointer_set *pset, unsigned key); static struct dyn_pointer_set * pointer_set_create (unsigned (*get_key) (const void *)); 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 { EAGER_PROPAGATION_ALGORITHM=0, INCLUSION_BASED_PRIORITY_ALGORITHM }; static int flag_alg_mode; static int flag_modu_merge_edges; static int flag_weak_inclusion; static int flag_use_existing_grouping; static gcov_unsigned_t mem_threshold; gcov_type gcov_find_new_ic_target (gcov_type caller_guid, gcov_type callee_guid); void __gcov_dyn_ipa_merge_add (gcov_type *dest, gcov_type *src, unsigned n_counters); void __gcov_dyn_ipa_merge_ior (gcov_type *dest, gcov_type *src, unsigned n_counters); void __gcov_dyn_ipa_merge_dc (gcov_type *dest, gcov_type *src, unsigned n_counters); void __gcov_dyn_ipa_merge_icall_topn (gcov_type *dest, gcov_type *src, unsigned n_counters); void __gcov_dyn_ipa_merge_single (gcov_type *dest, gcov_type *src, unsigned n_counters); void __gcov_dyn_ipa_merge_delta (gcov_type *dest, gcov_type *src, unsigned n_counters); /* Returns 0 if no dump is enabled. Returns 1 if text form graph dump is enabled. Returns 2 if .dot form dump is enabled. */ static int do_cgraph_dump (void) { const char *dyn_cgraph_dump = 0; if (__gcov_lipo_dump_cgraph) return __gcov_lipo_dump_cgraph; dyn_cgraph_dump = getenv ("GCOV_DYN_CGRAPH_DUMP"); if (!dyn_cgraph_dump || !strlen (dyn_cgraph_dump)) return 0; if (dyn_cgraph_dump[0] == '1') return 1; if (dyn_cgraph_dump[0] == '2') return 2; return 0; } static void init_dyn_cgraph_node (struct dyn_cgraph_node *node, gcov_type guid) { node->callees = 0; node->callers = 0; node->imported_modules = 0; node->guid = guid; node->visited = 0; } /* Return module_id. FUNC_GUID is the global unique id. This id is 1 based. 0 is the invalid id. */ static inline gcov_unsigned_t get_module_ident_from_func_glob_uid (gcov_type func_guid) { return EXTRACT_MODULE_ID_FROM_GLOBAL_ID (func_guid); } /* Return module_id for MODULE_INFO. */ static inline gcov_unsigned_t get_module_ident (const struct gcov_info *module_info) { return module_info->mod_info->ident; } /* Return intra-module function id given function global unique id FUNC_GUID. */ static inline gcov_unsigned_t get_intra_module_func_id (gcov_type func_guid) { return EXTRACT_FUNC_ID_FROM_GLOBAL_ID (func_guid); } /* Return the pointer to the dynamic call graph node for FUNC_GUID. */ static inline struct dyn_cgraph_node * get_cgraph_node (gcov_type func_guid) { gcov_unsigned_t mod_idx, func_id; mod_idx = get_module_ident_from_func_glob_uid (func_guid) - 1; /* This is to workaround: calls in __static_initialization_and_destruction should not be instrumented as the module id context for the callees have not setup yet -- this leads to mod_idx == (unsigned) (0 - 1). Multithreaded programs may also produce insane func_guid in the profile counter. */ if (mod_idx >= the_dyn_call_graph.num_modules) return 0; func_id = get_intra_module_func_id (func_guid); if (func_id > the_dyn_call_graph.sup_modules[mod_idx].max_func_ident) return 0; return (struct dyn_cgraph_node *) *(pointer_set_find_or_insert (the_dyn_call_graph.call_graph_nodes[mod_idx], func_id)); } static inline unsigned imp_mod_get_key (const void *p) { return ((const struct dyn_imp_mod *) p)->imp_mod->mod_info->ident; } static int imp_mod_set_insert (struct dyn_pointer_set *p, const struct gcov_info *imp_mod, double wt) { struct dyn_imp_mod **m = (struct dyn_imp_mod **) pointer_set_find_or_insert (p, get_module_ident (imp_mod)); if (*m) { (*m)->weight += wt; return 1; } else { *m = XNEW (struct dyn_imp_mod); (*m)->imp_mod = imp_mod; (*m)->weight = wt; p->n_elements++; return 0; } } /* Return the gcov_info pointer for module with id MODULE_ID. */ static inline struct gcov_info * get_module_info (gcov_unsigned_t module_id) { return the_dyn_call_graph.modules[module_id - 1]; } struct gcov_info *__gcov_list ATTRIBUTE_HIDDEN; static inline unsigned cgraph_node_get_key (const void *p) { return get_intra_module_func_id (((const struct dyn_cgraph_node *) p)->guid); } static inline unsigned gcov_info_get_key (const void *p) { return get_module_ident ((const struct gcov_info *)p); } /* The lineno_checksum value in P is the key for lineno_pointer_sets. */ static inline unsigned lineno_checksum_get_key (const void *p) { return ((const struct lineno_checksum_alias *) p)->lineno_checksum; } /* Create a new checksum_alias struct for function with GUID, FI_PTR, and ZERO_COUNT_FIXUP flag pointer. Prepends to list NEXT and returns new struct. */ static struct checksum_alias * new_checksum_alias (gcov_type guid, const struct gcov_fn_info *fi_ptr, char *zero_count_fixup, struct checksum_alias *next) { struct checksum_alias *alias = XNEW (struct checksum_alias); alias->next_alias = next; alias->fi_ptr = fi_ptr; alias->guid = guid; alias->zero_count_fixup = zero_count_fixup; return alias; } /* 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_COUNT_FIXUP flag pointer. */ static struct checksum_alias_info * cfg_checksum_insert (unsigned cfg_checksum, gcov_type guid, const struct gcov_fn_info *fi_ptr, char *zero_count_fixup, struct checksum_alias_info *list) { struct checksum_alias_info *alias_info; alias_info = find_cfg_checksum (list, cfg_checksum); if (alias_info) { gcc_assert (alias_info->alias_list); alias_info->alias_list = new_checksum_alias (guid, fi_ptr, zero_count_fixup, alias_info->alias_list); return list; } else { 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_count_fixup, NULL); return alias_info; } } /* Insert a new checksum_alias struct into lineno_pointer_sets for function with LINENO_CHECKSUM and CFG_CHECKSUM with associated GUID, FI_PTR, and ZERO_COUNT_FIXUP flag pointer. */ static void checksum_set_insert (unsigned lineno_checksum, unsigned cfg_checksum, gcov_type guid, const struct gcov_fn_info *fi_ptr, char *zero_count_fixup) { struct dyn_pointer_set *p = the_dyn_call_graph.lineno_pointer_sets; if (!p) the_dyn_call_graph.lineno_pointer_sets = p = pointer_set_create (lineno_checksum_get_key); struct lineno_checksum_alias **m = (struct lineno_checksum_alias **) pointer_set_find_or_insert (p, lineno_checksum); if (*m) { (*m)->cfg_checksum_list = cfg_checksum_insert (cfg_checksum, guid, fi_ptr, zero_count_fixup, (*m)->cfg_checksum_list); } else { *m = XNEW (struct lineno_checksum_alias); (*m)->lineno_checksum = lineno_checksum; (*m)->cfg_checksum_list = cfg_checksum_insert (cfg_checksum, guid, fi_ptr, zero_count_fixup, NULL); p->n_elements++; } } static struct dyn_pointer_set * get_exported_to (unsigned module_ident) { gcc_assert (module_ident != 0); return the_dyn_call_graph.sup_modules[module_ident - 1].exported_to; } static struct dyn_pointer_set * create_exported_to (unsigned module_ident) { struct dyn_pointer_set *p; gcc_assert (module_ident != 0); p = pointer_set_create (gcov_info_get_key); the_dyn_call_graph.sup_modules[module_ident - 1].exported_to = p; return p; } static struct dyn_pointer_set * get_imported_modus (unsigned module_ident) { struct dyn_pointer_set *p; struct gcov_info *gi_ptr; gcc_assert (module_ident != 0); p = the_dyn_call_graph.sup_modules[module_ident - 1].imported_modules; if (p) return p; the_dyn_call_graph.sup_modules[module_ident - 1].imported_modules = p = pointer_set_create (imp_mod_get_key); gi_ptr = the_dyn_call_graph.modules[module_ident - 1]; /* make the modules an auxiliay module to itself. */ imp_mod_set_insert (p, gi_ptr, 0); return p; } /* Initialize dynamic call graph. */ static void init_dyn_call_graph (void) { unsigned num_modules = 0; unsigned max_module_id = 0; struct gcov_info *gi_ptr; const char *env_str; int do_dump = (do_cgraph_dump () != 0); the_dyn_call_graph.call_graph_nodes = 0; the_dyn_call_graph.modules = 0; the_dyn_call_graph.num_nodes_executed = 0; flag_alg_mode = __gcov_lipo_grouping_algorithm; flag_modu_merge_edges = __gcov_lipo_merge_modu_edges; flag_weak_inclusion = __gcov_lipo_weak_inclusion; mem_threshold = __gcov_lipo_max_mem * 1.25; gi_ptr = __gcov_list; for (; gi_ptr; gi_ptr = gi_ptr->next) { unsigned mod_id = get_module_ident (gi_ptr); num_modules++; if (max_module_id < mod_id) max_module_id = mod_id; } if (num_modules < max_module_id) num_modules = max_module_id; the_dyn_call_graph.num_modules = num_modules; the_dyn_call_graph.modules = XNEWVEC (struct gcov_info *, num_modules); memset (the_dyn_call_graph.modules, 0, num_modules * sizeof (struct gcov_info*)); the_dyn_call_graph.sup_modules = XNEWVEC (struct dyn_module_info, num_modules); memset (the_dyn_call_graph.sup_modules, 0, num_modules * sizeof (struct dyn_module_info)); the_dyn_call_graph.call_graph_nodes = XNEWVEC (struct dyn_pointer_set *, num_modules); gi_ptr = __gcov_list; if ((env_str = getenv ("GCOV_DYN_ALG"))) { flag_alg_mode = atoi (env_str); if ((env_str = getenv ("GCOV_DYN_MERGE_EDGES"))) flag_modu_merge_edges = atoi (env_str); if ((env_str = getenv ("GCOV_DYN_WEAK_INCLUSION"))) flag_weak_inclusion = atoi (env_str); if (do_dump) fprintf (stderr, "!!!! Using ALG=%d merge_edges=%d weak_inclusion=%d. \n", flag_alg_mode, flag_modu_merge_edges, flag_weak_inclusion); } if (do_dump) fprintf (stderr, "Group mem limit: %u KB \n", __gcov_lipo_max_mem); if (do_dump) fprintf (stderr, "COMDAT fixup algorithm: %u\n", __gcov_lipo_comdat_algorithm); for (; gi_ptr; gi_ptr = gi_ptr->next) { /* mod_idx is module_ident - 1. */ unsigned j, mod_id, mod_idx, max_func_ident = 0; struct dyn_cgraph_node *node; /* initialize flags field. */ gi_ptr->mod_info->flags = 0; mod_id = get_module_ident (gi_ptr); if (do_dump) fprintf (stderr, "Module %s %d uses %u KB memory in parsing\n", gi_ptr->mod_info->source_filename, mod_id, gi_ptr->mod_info->ggc_memory); if (mod_id == 0) { fprintf (stderr, "Bad module_ident of 0. Skipping.\n"); continue; } mod_idx = mod_id - 1; the_dyn_call_graph.modules[mod_idx] = gi_ptr; the_dyn_call_graph.call_graph_nodes[mod_idx] = pointer_set_create (cgraph_node_get_key); for (j = 0; j < gi_ptr->n_functions; j++) { const struct gcov_fn_info *fi_ptr = gi_ptr->functions[j]; *(pointer_set_find_or_insert (the_dyn_call_graph.call_graph_nodes[mod_idx], fi_ptr->ident)) = node = XNEW (struct dyn_cgraph_node); the_dyn_call_graph.call_graph_nodes[mod_idx]->n_elements++; init_dyn_cgraph_node (node, GEN_FUNC_GLOBAL_ID (gi_ptr->mod_info->ident, fi_ptr->ident)); if (fi_ptr->ident > max_func_ident) max_func_ident = fi_ptr->ident; } the_dyn_call_graph.sup_modules[mod_idx].max_func_ident = max_func_ident; if (flag_alg_mode == INCLUSION_BASED_PRIORITY_ALGORITHM) { struct dyn_module_info *sup_module = &(the_dyn_call_graph.sup_modules[mod_idx]); sup_module->group_ggc_mem = gi_ptr->mod_info->ggc_memory; sup_module->imported_modules = 0; sup_module->exported_to = 0; } } } /* Free up memory allocated for dynamic call graph. */ void __gcov_finalize_dyn_callgraph (void) { unsigned i; for (i = 0; i < the_dyn_call_graph.num_modules; i++) { struct gcov_info *gi_ptr = the_dyn_call_graph.modules[i]; const struct gcov_fn_info *fi_ptr; unsigned f_ix; if (gi_ptr == NULL) continue; for (f_ix = 0; f_ix < gi_ptr->n_functions; f_ix++) { struct dyn_cgraph_node *node; struct dyn_cgraph_edge *callees, *next_callee; fi_ptr = gi_ptr->functions[f_ix]; node = (struct dyn_cgraph_node *) *(pointer_set_find_or_insert (the_dyn_call_graph.call_graph_nodes[i], fi_ptr->ident)); gcc_assert (node); callees = node->callees; if (!callees) continue; while (callees != 0) { next_callee = callees->next_callee; XDELETE (callees); callees = next_callee; } if (node->imported_modules) pointer_set_destroy (node->imported_modules); } if (the_dyn_call_graph.call_graph_nodes[i]) pointer_set_destroy (the_dyn_call_graph.call_graph_nodes[i]); /* Now delete sup modules */ if (the_dyn_call_graph.sup_modules[i].imported_modules) pointer_set_destroy (the_dyn_call_graph.sup_modules[i].imported_modules); if (flag_alg_mode == INCLUSION_BASED_PRIORITY_ALGORITHM && the_dyn_call_graph.sup_modules[i].exported_to) pointer_set_destroy_not_free_value_pointer (the_dyn_call_graph.sup_modules[i].exported_to); } XDELETEVEC (the_dyn_call_graph.call_graph_nodes); XDELETEVEC (the_dyn_call_graph.sup_modules); XDELETEVEC (the_dyn_call_graph.modules); } /* Add outgoing edge OUT_EDGE for caller node CALLER. */ static void gcov_add_out_edge (struct dyn_cgraph_node *caller, struct dyn_cgraph_edge *out_edge) { if (!caller->callees) caller->callees = out_edge; else { out_edge->next_callee = caller->callees; caller->callees = out_edge; } } /* Add incoming edge IN_EDGE for callee node CALLEE. */ static void gcov_add_in_edge (struct dyn_cgraph_node *callee, struct dyn_cgraph_edge *in_edge) { if (!callee->callers) callee->callers = in_edge; else { in_edge->next_caller = callee->callers; callee->callers = in_edge; } } /* Add a call graph edge between caller CALLER and callee CALLEE. The edge count is COUNT and INDIRECT flags whether the call was direct or indirect. */ static void gcov_add_cgraph_edge (struct dyn_cgraph_node *caller, struct dyn_cgraph_node *callee, gcov_type count, int indirect) { struct dyn_cgraph_edge *new_edge = XNEW (struct dyn_cgraph_edge); new_edge->caller = caller; new_edge->callee = callee; new_edge->count = count; new_edge->next_caller = 0; new_edge->next_callee = 0; new_edge->indirect = indirect; gcov_add_out_edge (caller, new_edge); gcov_add_in_edge (callee, new_edge); } /* Add call graph edges from direct calls for caller CALLER. DIR_CALL_COUNTERS is the array of call counters. N_COUNTS is the number of counters. */ static void gcov_build_callgraph_dc_fn (struct dyn_cgraph_node *caller, gcov_type *dir_call_counters, unsigned n_counts) { unsigned i; for (i = 0; i < n_counts; i += 2) { struct dyn_cgraph_node *callee; gcov_type count; gcov_type callee_guid = dir_call_counters[i]; count = dir_call_counters[i + 1]; if (count == 0) { total_zero_count++; continue; } callee = get_cgraph_node (callee_guid); if (!callee) { total_insane_count++; continue; } gcov_add_cgraph_edge (caller, callee, count, 0); } } /* Add call graph edges from indirect calls for caller CALLER. ICALL_COUNTERS is the array of icall counters. N_COUNTS is the number of counters. */ static void gcov_build_callgraph_ic_fn (struct dyn_cgraph_node *caller, gcov_type *icall_counters, unsigned n_counts) { unsigned i, j; for (i = 0; i < n_counts; i += GCOV_ICALL_TOPN_NCOUNTS) { gcov_type *value_array = &icall_counters[i + 1]; for (j = 0; j < GCOV_ICALL_TOPN_NCOUNTS - 1; j += 2) { struct dyn_cgraph_node *callee; gcov_type count; gcov_type callee_guid = value_array[j]; count = value_array[j + 1]; /* Do not update zero count edge count * as it means there is no target in this entry. */ if (count == 0) continue; callee = get_cgraph_node (callee_guid); if (!callee) { total_insane_count++; continue; } gcov_add_cgraph_edge (caller, callee, count, 1); } } } /* Build the dynamic call graph and update ZERO_COUNTS flags. */ static void gcov_build_callgraph (char **zero_counts) { struct gcov_info *gi_ptr; unsigned m_ix; init_dyn_call_graph (); for (m_ix = 0; m_ix < the_dyn_call_graph.num_modules; m_ix++) { const struct gcov_fn_info *fi_ptr; unsigned f_ix, i; gi_ptr = the_dyn_call_graph.modules[m_ix]; if (gi_ptr == NULL) continue; for (f_ix = 0; f_ix < gi_ptr->n_functions; f_ix++) { struct dyn_cgraph_node *caller; const struct gcov_ctr_info *ci_ptr = 0; fi_ptr = gi_ptr->functions[f_ix]; ci_ptr = fi_ptr->ctrs; caller = (struct dyn_cgraph_node *) *(pointer_set_find_or_insert (the_dyn_call_graph.call_graph_nodes[m_ix], fi_ptr->ident)); gcc_assert (caller); for (i = 0; i < GCOV_COUNTERS; i++) { if (!gi_ptr->merge[i]) continue; if (i == GCOV_COUNTER_DIRECT_CALL) gcov_build_callgraph_dc_fn (caller, ci_ptr->values, ci_ptr->num); if (i == GCOV_COUNTER_ICALL_TOPNV) gcov_build_callgraph_ic_fn (caller, ci_ptr->values, ci_ptr->num); if (i == GCOV_COUNTER_ARCS) { gcov_type total_arc_count = 0; unsigned arc; for (arc = 0; arc < ci_ptr->num; arc++) total_arc_count += ci_ptr->values[arc]; if (total_arc_count != 0) the_dyn_call_graph.num_nodes_executed++; if (fixup_type) { char *zero_count_fixup = NULL; /* Passing in a non-NULL zero_count_fixup pointer indicates that the counts were all zero for this function, and the fixup routine will set the flag if the function's counters are updated to non-zero values. */ if (total_arc_count == 0) zero_count_fixup = &zero_counts[m_ix][f_ix]; checksum_set_insert (fi_ptr->lineno_checksum, fi_ptr->cfg_checksum, caller->guid, fi_ptr, zero_count_fixup); } } ci_ptr++; } } } } static inline size_t hash1 (unsigned p, unsigned long max, unsigned long logmax) { const unsigned long long A = 0x9e3779b97f4a7c16ull; const unsigned long long shift = 64 - logmax; return ((A * (unsigned long) p) >> shift) & (max - 1); } /* Allocate an empty imported-modules set. */ static struct dyn_pointer_set * pointer_set_create (unsigned (*get_key) (const void *)) { struct dyn_pointer_set *result = XNEW (struct dyn_pointer_set); result->n_elements = 0; result->log_slots = 8; result->n_slots = (size_t) 1 << result->log_slots; result->slots = XNEWVEC (void *, result->n_slots); memset (result->slots, 0, sizeof (void *) * result->n_slots); result->get_key = get_key; return result; } /* Reclaim all memory associated with PSET. */ static void pointer_set_destroy (struct dyn_pointer_set *pset) { size_t i; for (i = 0; i < pset->n_slots; i++) if (pset->slots[i]) XDELETE (pset->slots[i]); XDELETEVEC (pset->slots); XDELETE (pset); } /* Reclaim the memory of PSET but not the value pointer. */ static void pointer_set_destroy_not_free_value_pointer (struct dyn_pointer_set *pset) { XDELETEVEC (pset->slots); XDELETE (pset); } /* Subroutine of pointer_set_find_or_insert. Return the insertion slot for KEY into an empty element of SLOTS, an array of length N_SLOTS. */ static inline size_t insert_aux (unsigned key, void **slots, size_t n_slots, size_t log_slots, unsigned (*get_key) (const void *)) { size_t n = hash1 (key, n_slots, log_slots); while (1) { if (slots[n] == 0 || get_key (slots[n]) == key) return n; else { ++n; if (n == n_slots) n = 0; } } } /* Find slot for KEY. KEY must be nonnull. */ static void ** pointer_set_find_or_insert (struct dyn_pointer_set *pset, unsigned key) { size_t n; /* For simplicity, expand the set even if KEY is already there. This can be superfluous but can happen at most once. */ if (pset->n_elements > pset->n_slots / 4) { size_t new_log_slots = pset->log_slots + 1; size_t new_n_slots = pset->n_slots * 2; void **new_slots = XNEWVEC (void *, new_n_slots); memset (new_slots, 0, sizeof (void *) * new_n_slots); size_t i; for (i = 0; i < pset->n_slots; ++i) { void *value = pset->slots[i]; if (!value) continue; n = insert_aux (pset->get_key (value), new_slots, new_n_slots, new_log_slots, pset->get_key); new_slots[n] = value; } XDELETEVEC (pset->slots); pset->n_slots = new_n_slots; pset->log_slots = new_log_slots; pset->slots = new_slots; } n = insert_aux (key, pset->slots, pset->n_slots, pset->log_slots, pset->get_key); return &pset->slots[n]; } /* Pass each pointer in PSET to the function in FN, together with the fixed parameters DATA1, DATA2, DATA3. If FN returns false, the iteration stops. */ static void pointer_set_traverse (const struct dyn_pointer_set *pset, int (*fn) (const void *, void *, void *, void *), void *data1, void *data2, void *data3) { size_t i; for (i = 0; i < pset->n_slots; ++i) if (pset->slots[i] && !fn (pset->slots[i], data1, data2, data3)) break; } /* Returns nonzero if PSET contains an entry with KEY as the key value. Collisions are resolved by linear probing. */ static int pointer_set_contains (const struct dyn_pointer_set *pset, unsigned key) { size_t n = hash1 (key, pset->n_slots, pset->log_slots); while (1) { if (pset->slots[n] == 0) return 0; else if (pset->get_key (pset->slots[n]) == key) return 1; else { ++n; if (n == pset->n_slots) n = 0; } } } /* Callback function to propagate import module (VALUE) from callee to caller's imported-module-set (DATA1). The weight is scaled by the scaling-factor (DATA2) before propagation, and accumulated into DATA3. */ static int gcov_propagate_imp_modules (const void *value, void *data1, void *data2, void *data3) { const struct dyn_imp_mod *m = (const struct dyn_imp_mod *) value; struct dyn_pointer_set *receiving_set = (struct dyn_pointer_set *) data1; double *scale = (double *) data2; double *sum = (double *) data3; double wt = m->weight; if (scale) wt *= *scale; if (sum) (*sum) += wt; imp_mod_set_insert (receiving_set, m->imp_mod, wt); return 1; } static int sort_by_count (const void *pa, const void *pb) { const struct dyn_cgraph_edge *edge_a = *(struct dyn_cgraph_edge * const *)pa; const struct dyn_cgraph_edge *edge_b = *(struct dyn_cgraph_edge * const *)pb; /* This can overvlow. */ /* return edge_b->count - edge_a->count; */ if (edge_b->count > edge_a->count) return 1; else if (edge_b->count == edge_a->count) return 0; else return -1; } /* Compute the hot callgraph edge threhold. */ static gcov_type gcov_compute_cutoff_count (void) { unsigned m_ix, capacity, i; unsigned num_edges = 0; gcov_type cutoff_count = 0; double total, cum, cum_cutoff; struct dyn_cgraph_edge **edges; struct gcov_info *gi_ptr; char *cutoff_str; char *num_perc_str; unsigned cutoff_perc; unsigned num_perc; int do_dump; capacity = 100; /* allocate an edge array */ edges = XNEWVEC (struct dyn_cgraph_edge*, capacity); /* First count the number of edges. */ for (m_ix = 0; m_ix < the_dyn_call_graph.num_modules; m_ix++) { const struct gcov_fn_info *fi_ptr; unsigned f_ix; gi_ptr = the_dyn_call_graph.modules[m_ix]; if (gi_ptr == NULL) continue; for (f_ix = 0; f_ix < gi_ptr->n_functions; f_ix++) { struct dyn_cgraph_node *node; struct dyn_cgraph_edge *callees; fi_ptr = gi_ptr->functions[f_ix]; node = (struct dyn_cgraph_node *) *(pointer_set_find_or_insert (the_dyn_call_graph.call_graph_nodes[m_ix], fi_ptr->ident)); gcc_assert (node); callees = node->callees; while (callees != 0) { num_edges++; if (num_edges < capacity) edges[num_edges - 1] = callees; else { capacity = capacity + (capacity >> 1); edges = (struct dyn_cgraph_edge **)xrealloc (edges, sizeof (void*) * capacity); edges[num_edges - 1] = callees; } callees = callees->next_callee; } } } /* Now sort */ qsort (edges, num_edges, sizeof (void *), sort_by_count); #define CUM_CUTOFF_PERCENT 80 #define MIN_NUM_EDGE_PERCENT 0 /* The default parameter value is 100 which is a reserved special value. When the cutoff parameter is 100, use the environment variable setting if it exists, otherwise, use the default value 80. */ if (__gcov_lipo_cutoff != 100) { cutoff_perc = __gcov_lipo_cutoff; num_perc = MIN_NUM_EDGE_PERCENT; } else { cutoff_str = getenv ("GCOV_DYN_CGRAPH_CUTOFF"); if (cutoff_str && strlen (cutoff_str)) { if ((num_perc_str = strchr (cutoff_str, ':'))) { *num_perc_str = '\0'; num_perc_str++; } cutoff_perc = atoi (cutoff_str); if (num_perc_str) num_perc = atoi (num_perc_str); else num_perc = MIN_NUM_EDGE_PERCENT; } else { cutoff_perc = CUM_CUTOFF_PERCENT; num_perc = MIN_NUM_EDGE_PERCENT; } } total = 0; cum = 0; for (i = 0; i < num_edges; i++) total += edges[i]->count; cum_cutoff = (total * cutoff_perc)/100; do_dump = (do_cgraph_dump () != 0); for (i = 0; i < num_edges; i++) { cum += edges[i]->count; if (do_dump) fprintf (stderr, "// edge[%d] count = %.0f [%llx --> %llx]\n", i, (double) edges[i]->count, (long long) edges[i]->caller->guid, (long long) edges[i]->callee->guid); if (cum >= cum_cutoff && (i * 100 >= num_edges * num_perc)) { cutoff_count = edges[i]->count; break; } } if (do_dump) fprintf (stderr,"cum count cutoff = %d%%, minimal num edge cutoff = %d%%\n", cutoff_perc, num_perc); if (do_dump) fprintf (stderr, "// total = %.0f cum = %.0f cum/total = %.0f%%" " cutoff_count = %lld [total edges: %d hot edges: %d perc: %d%%]\n" " total_zero_count_edges = %d total_insane_count_edgess = %d\n" " total_nodes_executed = %d\n", total, cum, (cum * 100)/total, (long long) cutoff_count, num_edges, i, (i * 100)/num_edges, total_zero_count, total_insane_count, the_dyn_call_graph.num_nodes_executed); XDELETEVEC (edges); return cutoff_count; } /* Return the imported module set for NODE. */ static struct dyn_pointer_set * gcov_get_imp_module_set (struct dyn_cgraph_node *node) { if (!node->imported_modules) node->imported_modules = pointer_set_create (imp_mod_get_key); return node->imported_modules; } /* Return the imported module set for MODULE MI. */ static struct dyn_pointer_set * gcov_get_module_imp_module_set (struct dyn_module_info *mi) { if (!mi->imported_modules) mi->imported_modules = pointer_set_create (imp_mod_get_key); return mi->imported_modules; } /* Callback function to mark if a module needs to be exported. */ static int gcov_mark_export_modules (const void *value, void *data1 ATTRIBUTE_UNUSED, void *data2 ATTRIBUTE_UNUSED, void *data3 ATTRIBUTE_UNUSED) { const struct gcov_info *module_info = ((const struct dyn_imp_mod *) value)->imp_mod; SET_MODULE_EXPORTED (module_info->mod_info); return 1; } struct gcov_import_mod_array { const struct dyn_imp_mod **imported_modules; struct gcov_info *importing_module; unsigned len; }; /* Callback function to compute pointer set size. */ static int gcov_compute_mset_size (const void *value ATTRIBUTE_UNUSED, void *data1, void *data2 ATTRIBUTE_UNUSED, void *data3 ATTRIBUTE_UNUSED) { unsigned *len = (unsigned *) data1; (*len)++; return 1; } /* Callback function to collect imported modules. */ static int gcov_collect_imported_modules (const void *value, void *data1, void *data2 ATTRIBUTE_UNUSED, void *data3 ATTRIBUTE_UNUSED) { struct gcov_import_mod_array *out_array; const struct dyn_imp_mod *m = (const struct dyn_imp_mod *) value; out_array = (struct gcov_import_mod_array *) data1; if (m->imp_mod != out_array->importing_module) { out_array->imported_modules[out_array->len++] = m; /* Sanity check that the importing (primary) module is not actually the same as the new aux module. This could happen if we accidentally read in the same gcda file twice. */ gcc_assert (m->imp_mod->mod_info->ident != out_array->importing_module->mod_info->ident); } return 1; } /* Comparator for sorting imported modules using weights. */ static int sort_by_module_wt (const void *pa, const void *pb) { const struct dyn_imp_mod *m_a = *((const struct dyn_imp_mod * const *) pa); const struct dyn_imp_mod *m_b = *((const struct dyn_imp_mod * const *) pb); /* We want to sort in descending order of weights. */ if (m_a->weight < m_b->weight) return +1; if (m_a->weight > m_b->weight) return -1; return get_module_ident (m_a->imp_mod) - get_module_ident (m_b->imp_mod); } /* Return a dynamic array of imported modules that is sorted for the importing module MOD_INFO. The length of the array is returned in *LEN. */ const struct dyn_imp_mod ** gcov_get_sorted_import_module_array (struct gcov_info *mod_info, unsigned *len) { unsigned mod_idx; struct dyn_module_info *sup_mod_info; unsigned array_len = 0; struct gcov_import_mod_array imp_array; mod_idx = get_module_ident (mod_info) - 1; sup_mod_info = &the_dyn_call_graph.sup_modules[mod_idx]; if (sup_mod_info->imported_modules == 0) return 0; pointer_set_traverse (sup_mod_info->imported_modules, gcov_compute_mset_size, &array_len, 0, 0); imp_array.imported_modules = XNEWVEC (const struct dyn_imp_mod *, array_len); imp_array.len = 0; imp_array.importing_module = mod_info; pointer_set_traverse (sup_mod_info->imported_modules, gcov_collect_imported_modules, &imp_array, 0, 0); *len = imp_array.len; qsort (imp_array.imported_modules, imp_array.len, sizeof (void *), sort_by_module_wt); return imp_array.imported_modules; } /* Compute modules that are needed for NODE (for cross module inlining). CUTTOFF_COUNT is the call graph edge count cutoff value. IMPORT_SCALE is the scaling-factor (percent) by which to scale the weights of imported modules of a callee before propagating them to the caller, if the callee and caller are in different modules. Each imported module is assigned a weight that corresponds to the expected benefit due to cross-module inlining. When the imported modules are written out, they are sorted with highest weight first. The following example illustrates how the weight is computed: Suppose we are processing call-graph node A. It calls function B 50 times, which calls function C 1000 times, and function E 800 times. Lets say B has another in-edge from function D, with edge-count of 50. Say all the functions are in separate modules (modules a, b, c, d, e, respectively): D | | 50 | 50 v 1000 A --------> B ----------> C | | 800 | v E Nodes are processed in depth-first order, so when processing A, we first process B. For node B, we are going to add module c to the imported-module set, with weight 1000 (edge-count), and module e with weight 800. Coming back to A, we are going to add the imported-module-set of B to A, after doing some scaling. The first scaling factor comes from the fact that A calls B 50 times, but B has in-edge-count total of 100. So this scaling factor is 50/100 = 0.5 The second scaling factor is that since B is in a different module than A, we want to slightly downgrade imported modules of B, before adding to the imported-modules set of A. This scaling factor has a default value of 50% (can be set via env variable GCOV_DYN_IMPORT_SCALE). So we end up adding modules c and e to the imported-set of A, with weights 0.5*0.5*1000=250 and 0.5*0.5*800=200, respectively. Next, we have to add module b itself to A. The weight is computed as the edge-count plus the sum of scaled-weights of all modules in the imported-module set of B, i.e., 50 + 250 + 200 = 500. In computing the weight of module b, we add the sum of scaled-weights of imported modules of b, because it doesn't make sense to import c, e in module a, until module b is imported. */ static void gcov_process_cgraph_node (struct dyn_cgraph_node *node, gcov_type cutoff_count, unsigned import_scale) { unsigned mod_id; struct dyn_cgraph_edge *callees; struct dyn_cgraph_edge *callers; node->visited = 1; node->sum_in_count = 0; callers = node->callers; while (callers) { node->sum_in_count += callers->count; callers = callers->next_caller; } callees = node->callees; mod_id = get_module_ident_from_func_glob_uid (node->guid); while (callees) { if (!callees->callee->visited) gcov_process_cgraph_node (callees->callee, cutoff_count, import_scale); callees = callees->next_callee; } callees = node->callees; while (callees) { if (callees->count >= cutoff_count) { unsigned callee_mod_id; struct dyn_pointer_set *imp_modules = gcov_get_imp_module_set (node); callee_mod_id = get_module_ident_from_func_glob_uid (callees->callee->guid); double callee_mod_wt = (double) callees->count; if (callees->callee->imported_modules) { double scale = ((double) callees->count) / ((double) callees->callee->sum_in_count); /* Reduce weight if callee is in different module. */ if (mod_id != callee_mod_id) scale = (scale * import_scale) / 100.0; pointer_set_traverse (callees->callee->imported_modules, gcov_propagate_imp_modules, imp_modules, &scale, &callee_mod_wt); } if (mod_id != callee_mod_id) { struct gcov_info *callee_mod_info = get_module_info (callee_mod_id); if (callee_mod_info) imp_mod_set_insert (imp_modules, callee_mod_info, callee_mod_wt); } } callees = callees->next_callee; } } static void gcov_compute_module_groups_eager_propagation (gcov_type); static void gcov_compute_module_groups_inclusion_based_with_priority (gcov_type); /* dyn_fibheap */ static void dyn_fibheap_ins_root (dyn_fibheap_t, fibnode_t); static void dyn_fibheap_rem_root (dyn_fibheap_t, fibnode_t); static void dyn_fibheap_consolidate (dyn_fibheap_t); static void dyn_fibheap_link (dyn_fibheap_t, fibnode_t, fibnode_t); static fibnode_t dyn_fibheap_extr_min_node (dyn_fibheap_t); static int dyn_fibheap_compare (dyn_fibheap_t, fibnode_t, fibnode_t); static int dyn_fibheap_comp_data (dyn_fibheap_t, dyn_fibheapkey_t, void *, fibnode_t); static fibnode_t fibnode_new (void); static void fibnode_insert_after (fibnode_t, fibnode_t); #define fibnode_insert_before(a, b) fibnode_insert_after (a->left, b) static fibnode_t fibnode_remove (fibnode_t); /* Create a new fibonacci heap. */ static dyn_fibheap_t dyn_fibheap_new (void) { return (dyn_fibheap_t) xcalloc (1, sizeof (struct dyn_fibheap)); } /* Create a new fibonacci heap node. */ static fibnode_t fibnode_new (void) { fibnode_t node; node = (fibnode_t) xcalloc (1, sizeof *node); node->left = node; node->right = node; return node; } static inline int dyn_fibheap_compare (dyn_fibheap_t heap ATTRIBUTE_UNUSED, fibnode_t a, fibnode_t b) { if (a->key < b->key) return -1; if (a->key > b->key) return 1; return 0; } static inline int dyn_fibheap_comp_data (dyn_fibheap_t heap, dyn_fibheapkey_t key, void *data, fibnode_t b) { struct fibnode a; a.key = key; a.data = data; return dyn_fibheap_compare (heap, &a, b); } /* Insert DATA, with priority KEY, into HEAP. */ static fibnode_t dyn_fibheap_insert (dyn_fibheap_t heap, dyn_fibheapkey_t key, void *data) { fibnode_t node; /* Create the new node. */ node = fibnode_new (); /* Set the node's data. */ node->data = data; node->key = key; /* Insert it into the root list. */ dyn_fibheap_ins_root (heap, node); /* If their was no minimum, or this key is less than the min, it's the new min. */ if (heap->min == 0 || node->key < heap->min->key) heap->min = node; heap->nodes++; return node; } /* Extract the data of the minimum node from HEAP. */ static void * dyn_fibheap_extract_min (dyn_fibheap_t heap) { fibnode_t z; void *ret = 0; /* If we don't have a min set, it means we have no nodes. */ if (heap->min != 0) { /* Otherwise, extract the min node, free the node, and return the node's data. */ z = dyn_fibheap_extr_min_node (heap); ret = z->data; free (z); } return ret; } /* Delete HEAP. */ static void dyn_fibheap_delete (dyn_fibheap_t heap) { while (heap->min != 0) free (dyn_fibheap_extr_min_node (heap)); free (heap); } /* Extract the minimum node of the heap. */ static fibnode_t dyn_fibheap_extr_min_node (dyn_fibheap_t heap) { fibnode_t ret = heap->min; fibnode_t x, y, orig; /* Attach the child list of the minimum node to the root list of the heap. If there is no child list, we don't do squat. */ for (x = ret->child, orig = 0; x != orig && x != 0; x = y) { if (orig == 0) orig = x; y = x->right; x->parent = 0; dyn_fibheap_ins_root (heap, x); } /* Remove the old root. */ dyn_fibheap_rem_root (heap, ret); heap->nodes--; /* If we are left with no nodes, then the min is 0. */ if (heap->nodes == 0) heap->min = 0; else { /* Otherwise, consolidate to find new minimum, as well as do the reorg work that needs to be done. */ heap->min = ret->right; dyn_fibheap_consolidate (heap); } return ret; } /* Insert NODE into the root list of HEAP. */ static void dyn_fibheap_ins_root (dyn_fibheap_t heap, fibnode_t node) { /* If the heap is currently empty, the new node becomes the singleton circular root list. */ if (heap->root == 0) { heap->root = node; node->left = node; node->right = node; return; } /* Otherwise, insert it in the circular root list between the root and it's right node. */ fibnode_insert_after (heap->root, node); } /* Remove NODE from the rootlist of HEAP. */ static void dyn_fibheap_rem_root (dyn_fibheap_t heap, fibnode_t node) { if (node->left == node) heap->root = 0; else heap->root = fibnode_remove (node); } /* Consolidate the heap. */ static void dyn_fibheap_consolidate (dyn_fibheap_t heap) { fibnode_t a[1 + 8 * sizeof (long)]; fibnode_t w; fibnode_t y; fibnode_t x; int i; int d; int D; D = 1 + 8 * sizeof (long); memset (a, 0, sizeof (fibnode_t) * D); while ((w = heap->root) != 0) { x = w; dyn_fibheap_rem_root (heap, w); d = x->degree; while (a[d] != 0) { y = a[d]; if (dyn_fibheap_compare (heap, x, y) > 0) { fibnode_t temp; temp = x; x = y; y = temp; } dyn_fibheap_link (heap, y, x); a[d] = 0; d++; } a[d] = x; } heap->min = 0; for (i = 0; i < D; i++) if (a[i] != 0) { dyn_fibheap_ins_root (heap, a[i]); if (heap->min == 0 || dyn_fibheap_compare (heap, a[i], heap->min) < 0) heap->min = a[i]; } } /* Make NODE a child of PARENT. */ static void dyn_fibheap_link (dyn_fibheap_t heap ATTRIBUTE_UNUSED, fibnode_t node, fibnode_t parent) { if (parent->child == 0) parent->child = node; else fibnode_insert_before (parent->child, node); node->parent = parent; parent->degree++; node->mark = 0; } static void fibnode_insert_after (fibnode_t a, fibnode_t b) { if (a == a->right) { a->right = b; a->left = b; b->right = a; b->left = a; } else { b->right = a->right; a->right->left = b; a->right = b; b->left = a; } } static fibnode_t fibnode_remove (fibnode_t node) { fibnode_t ret; if (node == node->left) ret = 0; else ret = node->left; if (node->parent != 0 && node->parent->child == node) node->parent->child = ret; node->right->left = node->left; node->left->right = node->right; node->parent = 0; node->left = node; node->right = node; return ret; } /* end of dyn_fibheap */ /* Compute module grouping using CUTOFF_COUNT as the hot edge threshold. */ static void gcov_compute_module_groups (gcov_type cutoff_count) { switch (flag_alg_mode) { case INCLUSION_BASED_PRIORITY_ALGORITHM: return gcov_compute_module_groups_inclusion_based_with_priority (cutoff_count); case EAGER_PROPAGATION_ALGORITHM: default: return gcov_compute_module_groups_eager_propagation (cutoff_count); } } static void modu_graph_add_edge (unsigned m_id, unsigned callee_m_id, gcov_type count) { struct modu_node *mnode; struct modu_node *callee_mnode; struct modu_edge *e; if (m_id == 0 || callee_m_id == 0) return; mnode = &the_dyn_call_graph.modu_nodes[m_id - 1]; callee_mnode = &the_dyn_call_graph.modu_nodes[callee_m_id - 1]; if (flag_modu_merge_edges) { struct modu_edge *callees = mnode->callees; while (callees) { if (callees->callee == callee_mnode) { callees->n_edges += 1; callees->sum_count += count; return; } callees = callees->next_callee; } } e = XNEW (struct modu_edge); e->caller = mnode; e->callee = callee_mnode; e->n_edges = 1; e->sum_count = count; e->next_callee = mnode->callees; e->next_caller = callee_mnode->callers; mnode->callees = e; callee_mnode->callers = e; e->visited = 0; } static void modu_graph_process_dyn_cgraph_node (struct dyn_cgraph_node *node, gcov_type cutoff_count) { unsigned m_id = get_module_ident_from_func_glob_uid (node->guid); struct dyn_cgraph_edge *callees; struct dyn_cgraph_node *callee; callees = node->callees; while (callees != 0) { callee = callees->callee; unsigned callee_m_id = get_module_ident_from_func_glob_uid (callee->guid); if (callee_m_id != m_id) { if (callees->count >= cutoff_count) modu_graph_add_edge (m_id, callee_m_id, callees->count); } callees = callees->next_callee; } } static void build_modu_graph (gcov_type cutoff_count) { unsigned m_ix; struct gcov_info *gi_ptr; unsigned n_modules = the_dyn_call_graph.num_modules; struct modu_node *modu_nodes; /* Create modu graph nodes/edges. */ modu_nodes = XCNEWVEC (struct modu_node, n_modules); the_dyn_call_graph.modu_nodes = modu_nodes; for (m_ix = 0; m_ix < n_modules; m_ix++) { const struct gcov_fn_info *fi_ptr; unsigned f_ix; gi_ptr = the_dyn_call_graph.modules[m_ix]; if (gi_ptr == NULL) continue; modu_nodes[m_ix].module = gi_ptr; for (f_ix = 0; f_ix < gi_ptr->n_functions; f_ix++) { struct dyn_cgraph_node *node; fi_ptr = gi_ptr->functions[f_ix]; node = (struct dyn_cgraph_node *) *(pointer_set_find_or_insert (the_dyn_call_graph.call_graph_nodes[m_ix], fi_ptr->ident)); if (!node) { fprintf (stderr, "Cannot find module_node (ix = %u)./n", m_ix); continue; } modu_graph_process_dyn_cgraph_node (node, cutoff_count); } } } /* Collect ggc_mem_size for the impored_module in VALUE if DATA1 (a pointer_set) is provided, only count these not in DATA1. Result is stored in DATA2. */ static int collect_ggc_mem_size (const void *value, void *data1, void *data2, void *data3 ATTRIBUTE_UNUSED) { const struct dyn_imp_mod *g = (const struct dyn_imp_mod *) value; struct dyn_pointer_set *s = (struct dyn_pointer_set *) data1; unsigned mod_id = get_module_ident (g->imp_mod); gcov_unsigned_t *size = (gcov_unsigned_t *) data2; if (s && pointer_set_contains (s, mod_id)) return 1; (*size) += g->imp_mod->mod_info->ggc_memory; return 1; } /* Get the group ggc_memory size of a imported list. */ static gcov_unsigned_t get_group_ggc_mem (struct dyn_pointer_set *s) { gcov_unsigned_t ggc_size = 0; pointer_set_traverse (s, collect_ggc_mem_size, 0, &ggc_size, 0); return ggc_size; } /* Get the group ggc_memory size of the unioned imported lists. */ static gcov_unsigned_t modu_union_ggc_size (unsigned t_mid, unsigned s_mid) { struct dyn_pointer_set *t_imported_mods = get_imported_modus (t_mid); struct dyn_pointer_set *s_imported_mods = get_imported_modus (s_mid); gcov_unsigned_t size = 0; pointer_set_traverse (s_imported_mods, collect_ggc_mem_size, t_imported_mods, &size, 0); size += get_group_ggc_mem (t_imported_mods); return size; } /* Insert one module (VALUE) to the target module (DATA1) */ static int modu_add_auxiliary_1 (const void *value, void *data1, void *data2, void *data3 ATTRIBUTE_UNUSED) { const struct dyn_imp_mod *src = (const struct dyn_imp_mod *) value; const struct gcov_info *src_modu = src->imp_mod; unsigned t_m_id = *(unsigned *) data1; struct dyn_pointer_set *t_imported_mods = get_imported_modus (t_m_id); double wt = (double) *(gcov_type*)data2; unsigned s_m_id = get_module_ident (src_modu); struct gcov_info **gp; struct dyn_pointer_set *s_exported_to; int already_have = 0; if (pointer_set_contains (t_imported_mods, s_m_id)) already_have = 1; /* Insert even it's already there. This is to update the wt. */ imp_mod_set_insert (t_imported_mods, src_modu, wt); if (already_have) return 1; /* add module t_m_id to s_m_id's exported list. */ s_exported_to = get_exported_to (s_m_id); if (!s_exported_to) s_exported_to = create_exported_to (s_m_id); gp = (struct gcov_info **) pointer_set_find_or_insert (s_exported_to, t_m_id); *gp = the_dyn_call_graph.modules[t_m_id - 1]; s_exported_to->n_elements++; return 1; } /* Insert module S_MID and it's imported modules to imported list of module T_MID. */ static void modu_add_auxiliary (unsigned t_mid, unsigned s_mid, gcov_type count) { struct dyn_pointer_set *s_imported_mods = get_imported_modus (s_mid); pointer_set_traverse (s_imported_mods, modu_add_auxiliary_1, &t_mid, &count, 0); /* Recompute the gcc_memory for the group. */ the_dyn_call_graph.sup_modules[t_mid - 1].group_ggc_mem = get_group_ggc_mem (get_imported_modus (t_mid)); } /* Check if inserting the module specified by DATA1 (including it's imported list to grouping VALUE, makes the ggc_memory size exceed the memory threshold. Return 0 if size is great than the thereshold and 0 otherwise. */ static int ps_check_ggc_mem (const void *value, void *data1, void *data2, void *data3 ATTRIBUTE_UNUSED) { const struct gcov_info *modu = (const struct gcov_info *) value; unsigned s_m_id = *(unsigned *) data1; unsigned *fail = (unsigned *) data2; unsigned m_id = get_module_ident (modu); gcov_unsigned_t new_ggc_size; new_ggc_size = modu_union_ggc_size (m_id, s_m_id); if (new_ggc_size > mem_threshold) { (*fail) = 1; return 0; } return 1; } /* Add module specified by DATA1 and it's imported list to the grouping specified by VALUE. */ static int ps_add_auxiliary (const void *value, void *data1, void *data2, void *data3) { const struct gcov_info *modu = (const struct gcov_info *) value; unsigned s_m_id = *(unsigned *) data1; unsigned m_id = get_module_ident (modu); int not_safe_to_insert = *(int *) data3; gcov_unsigned_t new_ggc_size; /* For strict inclusion, we know it's safe to insert. */ if (!not_safe_to_insert) { modu_add_auxiliary (m_id, s_m_id, *(gcov_type*)data2); return 1; } /* Check if we can do a partial insertion. */ new_ggc_size = modu_union_ggc_size (m_id, s_m_id); if (new_ggc_size > mem_threshold) return 1; modu_add_auxiliary (m_id, s_m_id, *(gcov_type*)data2); return 1; } /* Return 1 if insertion happened, otherwise 0. */ static int modu_edge_add_auxiliary (struct modu_edge *edge) { struct modu_node *node; struct modu_node *callee; struct gcov_info *node_modu; struct gcov_info *callee_modu; gcov_unsigned_t group_ggc_mem; gcov_unsigned_t new_ggc_size; struct dyn_pointer_set *node_imported_mods; struct dyn_pointer_set *node_exported_to; unsigned m_id, callee_m_id; int fail = 0; node = edge->caller; callee = edge->callee; node_modu = node->module; callee_modu = callee->module; m_id = get_module_ident (node_modu); if (m_id == 0) return 0; group_ggc_mem = the_dyn_call_graph.sup_modules[m_id - 1].group_ggc_mem; if (group_ggc_mem >= mem_threshold) return 0; node_imported_mods = get_imported_modus (m_id); /* Check if the callee is already included. */ callee_m_id = get_module_ident (callee_modu); if (pointer_set_contains (node_imported_mods, callee_m_id)) return 0; new_ggc_size = modu_union_ggc_size (m_id, callee_m_id); if (new_ggc_size > mem_threshold) return 0; /* check the size for the grouping that includes this node. */ node_exported_to = get_exported_to (m_id); if (node_exported_to) { pointer_set_traverse (node_exported_to, ps_check_ggc_mem, &callee_m_id, &fail, 0); if (fail && !flag_weak_inclusion) return 0; } /* Perform the insertion: first insert to node and then to all the exported_to nodes. */ modu_add_auxiliary (m_id, callee_m_id, edge->sum_count); if (node_exported_to) pointer_set_traverse (node_exported_to, ps_add_auxiliary, &callee_m_id, &(edge->sum_count), &fail); return 1; } static void compute_module_groups_inclusion_impl (void) { dyn_fibheap_t heap; unsigned i; unsigned n_modules = the_dyn_call_graph.num_modules; /* insert all the edges to the heap. */ heap = dyn_fibheap_new (); for (i = 0; i < n_modules; i++) { struct modu_edge * callees; struct modu_node *node = &the_dyn_call_graph.modu_nodes[i]; callees = node->callees; while (callees != 0) { dyn_fibheap_insert (heap, -1 * callees->sum_count, callees); callees = callees->next_callee; } } while (1) { struct modu_edge *curr = (struct modu_edge *) dyn_fibheap_extract_min (heap); if (!curr) break; if (curr->visited) continue; curr->visited = 1; modu_edge_add_auxiliary (curr); } dyn_fibheap_delete (heap); /* Now compute the export attribute */ for (i = 0; i < n_modules; i++) { struct dyn_module_info *mi = &the_dyn_call_graph.sup_modules[i]; if (mi->exported_to) SET_MODULE_EXPORTED (the_dyn_call_graph.modules[i]->mod_info); } } static void gcov_compute_module_groups_inclusion_based_with_priority (gcov_type cutoff_count) { build_modu_graph (cutoff_count); compute_module_groups_inclusion_impl (); } static void gcov_compute_module_groups_eager_propagation (gcov_type cutoff_count) { unsigned m_ix; struct gcov_info *gi_ptr; const char *import_scale_str; unsigned import_scale = __gcov_lipo_propagate_scale; /* Different from __gcov_lipo_cutoff handling, the environment variable here takes precedance */ import_scale_str = getenv ("GCOV_DYN_IMPORT_SCALE"); if (import_scale_str && strlen (import_scale_str)) import_scale = atoi (import_scale_str); for (m_ix = 0; m_ix < the_dyn_call_graph.num_modules; m_ix++) { const struct gcov_fn_info *fi_ptr; unsigned f_ix; gi_ptr = the_dyn_call_graph.modules[m_ix]; if (gi_ptr == NULL) continue; for (f_ix = 0; f_ix < gi_ptr->n_functions; f_ix++) { struct dyn_cgraph_node *node; fi_ptr = gi_ptr->functions[f_ix]; node = (struct dyn_cgraph_node *) *(pointer_set_find_or_insert (the_dyn_call_graph.call_graph_nodes[m_ix], fi_ptr->ident)); gcc_assert (node); if (node->visited) continue; gcov_process_cgraph_node (node, cutoff_count, import_scale); } } for (m_ix = 0; m_ix < the_dyn_call_graph.num_modules; m_ix++) { const struct gcov_fn_info *fi_ptr; unsigned f_ix; gi_ptr = the_dyn_call_graph.modules[m_ix]; if (gi_ptr == NULL) continue; for (f_ix = 0; f_ix < gi_ptr->n_functions; f_ix++) { struct dyn_cgraph_node *node; unsigned mod_id; struct dyn_pointer_set *imp_modules; fi_ptr = gi_ptr->functions[f_ix]; node = (struct dyn_cgraph_node *) *(pointer_set_find_or_insert (the_dyn_call_graph.call_graph_nodes[m_ix], fi_ptr->ident)); gcc_assert (node); if (!node->imported_modules) continue; mod_id = get_module_ident_from_func_glob_uid (node->guid); gcc_assert (mod_id == (m_ix + 1)); imp_modules = gcov_get_module_imp_module_set ( &the_dyn_call_graph.sup_modules[mod_id - 1]); pointer_set_traverse (node->imported_modules, gcov_propagate_imp_modules, imp_modules, 0, 0); } } /* Now compute the export attribute */ for (m_ix = 0; m_ix < the_dyn_call_graph.num_modules; m_ix++) { struct dyn_module_info *mi = &the_dyn_call_graph.sup_modules[m_ix]; if (mi->imported_modules) pointer_set_traverse (mi->imported_modules, gcov_mark_export_modules, 0, 0, 0); } } /* For each module, compute at random, the group of imported modules, that is of size at most MAX_GROUP_SIZE. */ static void gcov_compute_random_module_groups (unsigned max_group_size) { unsigned m_ix; if (max_group_size > the_dyn_call_graph.num_modules) max_group_size = the_dyn_call_graph.num_modules; for (m_ix = 0; m_ix < the_dyn_call_graph.num_modules; m_ix++) { struct dyn_pointer_set *imp_modules = gcov_get_module_imp_module_set (&the_dyn_call_graph.sup_modules[m_ix]); int cur_group_size = rand () % max_group_size; int i = 0; while (i < cur_group_size) { struct gcov_info *imp_mod_info; unsigned mod_idx = rand () % the_dyn_call_graph.num_modules; if (mod_idx == m_ix) continue; imp_mod_info = get_module_info (mod_idx + 1); if (imp_mod_info && !imp_mod_set_insert (imp_modules, imp_mod_info, 1.0)) i++; } } /* Now compute the export attribute */ for (m_ix = 0; m_ix < the_dyn_call_graph.num_modules; m_ix++) { struct dyn_module_info *mi = &the_dyn_call_graph.sup_modules[m_ix]; if (mi->imported_modules) pointer_set_traverse (mi->imported_modules, gcov_mark_export_modules, 0, 0, 0); } } #if 0 /* Write out MOD_INFO into the gcda file. IS_PRIMARY is a flag indicating if the module is the primary module in the group. */ static void gcov_write_module_info (const struct gcov_info *mod_info, unsigned is_primary) { gcov_unsigned_t len = 0, filename_len = 0, src_filename_len = 0, i; gcov_unsigned_t num_strings; gcov_unsigned_t *aligned_fname; struct gcov_module_info *module_info = mod_info->mod_info; filename_len = (strlen (module_info->da_filename) + sizeof (gcov_unsigned_t)) / sizeof (gcov_unsigned_t); src_filename_len = (strlen (module_info->source_filename) + sizeof (gcov_unsigned_t)) / sizeof (gcov_unsigned_t); len = filename_len + src_filename_len; len += 2; /* each name string is led by a length. */ num_strings = module_info->num_quote_paths + module_info->num_bracket_paths + module_info->num_system_paths + module_info->num_cpp_defines + module_info->num_cpp_includes + module_info->num_cl_args; len += gcov_compute_string_array_len (module_info->string_array, num_strings); len += 11; /* 11 more fields */ gcov_write_tag_length (GCOV_TAG_MODULE_INFO, len); gcov_write_unsigned (module_info->ident); gcov_write_unsigned (is_primary); if (flag_alg_mode == INCLUSION_BASED_PRIORITY_ALGORITHM && is_primary) SET_MODULE_INCLUDE_ALL_AUX (module_info); gcov_write_unsigned (module_info->flags); gcov_write_unsigned (module_info->lang); gcov_write_unsigned (module_info->ggc_memory); gcov_write_unsigned (module_info->num_quote_paths); gcov_write_unsigned (module_info->num_bracket_paths); gcov_write_unsigned (module_info->num_system_paths); gcov_write_unsigned (module_info->num_cpp_defines); gcov_write_unsigned (module_info->num_cpp_includes); gcov_write_unsigned (module_info->num_cl_args); /* Now write the filenames */ aligned_fname = (gcov_unsigned_t *) alloca ((filename_len + src_filename_len + 2) * sizeof (gcov_unsigned_t)); memset (aligned_fname, 0, (filename_len + src_filename_len + 2) * sizeof (gcov_unsigned_t)); aligned_fname[0] = filename_len; strcpy ((char*) (aligned_fname + 1), module_info->da_filename); aligned_fname[filename_len + 1] = src_filename_len; strcpy ((char*) (aligned_fname + filename_len + 2), module_info->source_filename); for (i = 0; i < (filename_len + src_filename_len + 2); i++) gcov_write_unsigned (aligned_fname[i]); /* Now write the string array. */ gcov_write_string_array (module_info->string_array, num_strings); } #endif /* Write out MOD_INFO and its imported modules into gcda file. */ void gcov_write_module_infos (struct gcov_info *mod_info) { unsigned imp_len = 0; const struct dyn_imp_mod **imp_mods; if (flag_alg_mode == INCLUSION_BASED_PRIORITY_ALGORITHM) SET_MODULE_INCLUDE_ALL_AUX (mod_info->mod_info); gcov_write_module_info (mod_info, 1); imp_mods = gcov_get_sorted_import_module_array (mod_info, &imp_len); if (imp_mods) { unsigned i; for (i = 0; i < imp_len; i++) { const struct gcov_info *imp_mod = imp_mods[i]->imp_mod; if (imp_mod != mod_info) gcov_write_module_info (imp_mod, 0); } free (imp_mods); } } /* Set to use module grouping from existing imports files in the profile directory. */ void set_use_existing_grouping (void); void set_use_existing_grouping (void) { flag_use_existing_grouping = 1; } #ifdef IN_GCOV_TOOL extern const char *get_source_profile_dir (void); /* find and open the imports files based on da_filename in GI_PTR. */ static FILE * open_imports_file (struct gcov_info *gi_ptr) { const char *gcda_name; char *imports_name; const char *source_dir = ""; if (gi_ptr == NULL || gi_ptr->mod_info == NULL) return NULL; gcda_name = gi_ptr->mod_info->da_filename; gcc_assert (gcda_name); source_dir = get_source_profile_dir (); gcc_assert (source_dir); imports_name = (char *) alloca (strlen (gcda_name) + strlen (source_dir) + strlen (".gcda.imports") + 2); strcpy (imports_name, source_dir); strcat (imports_name, "/"); strcat (imports_name, gcda_name); strcat (imports_name, ".gcda.imports"); return fopen (imports_name, "r"); } extern int get_module_id_from_name (const char *); #endif /* IN_GCOV_TOOL */ /* Use the module grouping from existing imports files in the profile directory. */ static void read_modu_groups_from_imports_files (void) { #ifdef IN_GCOV_TOOL unsigned m_ix; const int max_line_size = (1 << 12); char line[max_line_size]; init_dyn_call_graph (); for (m_ix = 0; m_ix < the_dyn_call_graph.num_modules; m_ix++) { struct gcov_info *gi_ptr = the_dyn_call_graph.modules[m_ix]; FILE *fd; struct dyn_pointer_set *imp_modules; char buf[8192]; if (gi_ptr == NULL) continue; imp_modules = gcov_get_module_imp_module_set (&the_dyn_call_graph.sup_modules[m_ix]); if ((fd = open_imports_file (gi_ptr)) != NULL) { #define MAX_MODU_SIZE 200000 int w = MAX_MODU_SIZE; int i = 0; while (fgets (line, max_line_size, fd) != NULL) { unsigned mod_id = 0; char *name = strtok (line, " \t\n"); if (name && (mod_id = get_module_id_from_name (name))) { struct gcov_info *imp_mod_info; unsigned mod_idx = mod_id - 1; if (mod_idx == m_ix) continue; imp_mod_info = get_module_info (mod_idx + 1); i++; imp_mod_set_insert (imp_modules, imp_mod_info, w - i); } } fclose (fd); } } /* Now compute the export attribute */ for (m_ix = 0; m_ix < the_dyn_call_graph.num_modules; m_ix++) { struct dyn_module_info *mi = &the_dyn_call_graph.sup_modules[m_ix]; if (mi->imported_modules) pointer_set_traverse (mi->imported_modules, gcov_mark_export_modules, 0, 0, 0); } #else /* !IN_GCOV_TOOL */ gcc_assert (0); #endif /* IN_GCOV_TOOL */ } /* Scan functions in MOD_INFO and return gcov_fn_info for matching FUNC_ID. */ static const struct gcov_fn_info * find_fn_info_from_func_id (struct gcov_info *mod_info, unsigned func_id) { unsigned j; for (j = 0; j < mod_info->n_functions; j++) { const struct gcov_fn_info *fi_ptr = mod_info->functions[j]; if (fi_ptr->ident == func_id) return fi_ptr; } gcc_assert (0); return NULL; } /* Look for a function in the same module as CALLER_GUID that has the same lineno and cfg checksums as CALLEE_GUID. Return the guid of the matching function if exactly one is found, 0 otherwise. */ gcov_type gcov_find_new_ic_target (gcov_type caller_guid, gcov_type callee_guid) { /* Obtain the callee's function info. */ unsigned callee_mod_id = get_module_ident_from_func_glob_uid (callee_guid); struct gcov_info *callee_mod_info = get_module_info (callee_mod_id); unsigned callee_func_id = get_intra_module_func_id (callee_guid); const struct gcov_fn_info *callee_fi_ptr = find_fn_info_from_func_id (callee_mod_info, callee_func_id); /* Obtain the list of checksum_alias structures for functions with the same lineno and cfg checksum as callee. */ struct dyn_pointer_set *p = the_dyn_call_graph.lineno_pointer_sets; gcc_assert (p); 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 = 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 module. */ 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; alias = alias->next_alias) { if (get_module_ident_from_func_glob_uid (alias->guid) == caller_mod_id) { /* Give up if we found multiple matches. */ if (new_guid) return 0; new_guid = alias->guid; } } /* We found exactly one match, return it. */ return new_guid; } /* If any of CALLER's indirect call counters in CI_PTR has a target that is not in CALLER's module group, see if we can find a copy of the function in CALLER's module. If so, replace the target to point to that copy. See comments for gcov_fixup_icall_profile on why we would want to do this. Return 1 if any icall profiles were updated, 0 otherwise. */ static int gcov_fixup_ic_fn (struct dyn_cgraph_node *caller, const struct gcov_ctr_info *ci_ptr) { unsigned i, j; int changed = 0; gcov_type *icall_counters = ci_ptr->values; unsigned n_counts = ci_ptr->num; int do_dump = (do_cgraph_dump () != 0); unsigned caller_mod_id = get_module_ident_from_func_glob_uid (caller->guid); struct dyn_pointer_set *imported_mods = get_imported_modus (caller_mod_id); for (i = 0; i < n_counts; i += GCOV_ICALL_TOPN_NCOUNTS) { gcov_type *value_array = &icall_counters[i + 1]; for (j = 0; j < GCOV_ICALL_TOPN_NCOUNTS - 1; j += 2) { struct dyn_cgraph_node *callee; gcov_type count; gcov_type callee_guid = value_array[j]; count = value_array[j + 1]; if (count == 0) continue; callee = get_cgraph_node (callee_guid); if (!callee) continue; /* Now check if callee is in the module group of caller. If so, no need for any fixup. */ unsigned callee_mod_id = get_module_ident_from_func_glob_uid (callee_guid); if (pointer_set_contains (imported_mods, callee_mod_id)) continue; /* Attempt to find a copy of callee in caller's module. */ gcov_type new_callee_guid = gcov_find_new_ic_target (caller->guid, callee_guid); if (do_dump == 1) { struct gcov_info *caller_mod_info = the_dyn_call_graph.modules[caller_mod_id - 1]; struct gcov_info *callee_mod_info = the_dyn_call_graph.modules[callee_mod_id - 1]; fprintf (stderr, "Fixup icall %u:%u -> %u:%u with count %lld " "(%s -> %s): ", caller_mod_id, get_intra_module_func_id (caller->guid), callee_mod_id, get_intra_module_func_id (callee_guid), (long long) count, caller_mod_info->mod_info->source_filename, callee_mod_info->mod_info->source_filename); if (!new_callee_guid) fprintf (stderr,"No target found\n"); else fprintf (stderr,"Found new target %u:%u (%llx)\n", get_module_ident_from_func_glob_uid (new_callee_guid), get_intra_module_func_id (new_callee_guid), (long long) new_callee_guid); } if (new_callee_guid) { /* Update the profile info and note the need for a profile counter rewrite. */ value_array[j] = new_callee_guid; changed = 1; } } } return changed; } /* Look for indirect call profiles that target callee's outside of the caller's module group, and see if we can find a copy of the function in caller's own module. If so, replace the profile target to point to that copy. This is useful when the callee is a COMDAT, in which case there should be a copy within CALLER's module. The linker would have selected a single copy of COMDAT and all indirect call profiles would target that copy of the callee, which might not end up in the module group of CALLER. Return 1 if any icall profiles were updated, 0 otherwise. */ static int gcov_fixup_icall_profile (void) { struct gcov_info *gi_ptr; unsigned m_ix; int changed = 0; for (m_ix = 0; m_ix < the_dyn_call_graph.num_modules; m_ix++) { const struct gcov_fn_info *fi_ptr; unsigned f_ix, i; gi_ptr = the_dyn_call_graph.modules[m_ix]; if (gi_ptr == NULL) continue; for (f_ix = 0; f_ix < gi_ptr->n_functions; f_ix++) { struct dyn_cgraph_node *caller; const struct gcov_ctr_info *ci_ptr = 0; fi_ptr = gi_ptr->functions[f_ix]; ci_ptr = fi_ptr->ctrs; caller = (struct dyn_cgraph_node *) *(pointer_set_find_or_insert (the_dyn_call_graph.call_graph_nodes[m_ix], fi_ptr->ident)); gcc_assert (caller); for (i = 0; i < GCOV_COUNTERS; i++) { if (!gi_ptr->merge[i]) continue; if (i == GCOV_COUNTER_ICALL_TOPNV) changed |= gcov_fixup_ic_fn (caller, ci_ptr); ci_ptr++; } } } return changed; } /* Create, zero-initialize and return an array to hold merged counter values. */ static struct gcov_ctr_info * init_merged_ctrs (void) { struct gcov_ctr_info *merged_ctrs = XNEWVEC (struct gcov_ctr_info, GCOV_COUNTERS); int i; for (i = 0; i < GCOV_COUNTERS; i++) { merged_ctrs[i].num = 0; merged_ctrs[i].values = NULL; } return merged_ctrs; } /* The profile merging function that just adds N_COUNTERS counters from array SRC to those in DEST. Adapted from __gcov_merge_add. */ void __gcov_dyn_ipa_merge_add (gcov_type *dest, gcov_type *src, unsigned n_counters) { for (; n_counters; dest++, src++, n_counters--) *dest += *src; } /* The profile merging function that just ors N_COUNTERS counters from array SRC to those in DEST. Adapted from __gcov_merge_ior. */ void __gcov_dyn_ipa_merge_ior (gcov_type *dest, gcov_type *src, unsigned n_counters) { for (; n_counters; dest++, src++, n_counters--) *dest |= *src; } /* The profile merging function that just merges N_COUNTERS direct call counters from array SRC to those in DEST. Adapted from __gcov_merge_dc. */ void __gcov_dyn_ipa_merge_dc (gcov_type *dest, gcov_type *src, unsigned n_counters) { unsigned i; gcc_assert (!(n_counters % 2)); for (i = 0; i < n_counters; i += 2) { gcov_type global_id = src[i]; if (!global_id) continue; /* Simply skip non-matching call targets. */ if (dest[i] && dest[i] != global_id) { continue; } dest[i] = global_id; dest[i + 1] += src[i + 1]; } } /* The profile merging function that just merges N_COUNTERS indirect call counters from array SRC to those in DEST. Adapted from __gcov_merge_icall_topn. */ void __gcov_dyn_ipa_merge_icall_topn (gcov_type *dest, gcov_type *src, unsigned n_counters) { unsigned i, j, k, m; gcc_assert (!(n_counters % GCOV_ICALL_TOPN_NCOUNTS)); for (i = 0; i < n_counters; i += GCOV_ICALL_TOPN_NCOUNTS) { /* Skip the number_of_eviction entry (in dest[i]). */ gcov_type *value_array = &dest[i + 1]; unsigned tmp_size = 2 * (GCOV_ICALL_TOPN_NCOUNTS - 1); gcov_type *tmp_array = (gcov_type *) alloca (tmp_size * sizeof (gcov_type)); for (j = 0; j < tmp_size; j++) tmp_array[j] = 0; for (j = 0; j < GCOV_ICALL_TOPN_NCOUNTS - 1; j += 2) { tmp_array[j] = value_array[j]; tmp_array[j + 1] = value_array [j + 1]; } /* Skip the number_of_eviction entry (in src[i]). */ gcov_type *src_value_array = &src[i + 1]; for (k = 0; k < GCOV_ICALL_TOPN_NCOUNTS - 1; k += 2) { int found = 0; gcov_type global_id = src_value_array[k]; gcov_type call_count = src_value_array[k + 1]; for (m = 0; m < j; m += 2) { if (tmp_array[m] == global_id) { found = 1; tmp_array[m + 1] += call_count; break; } } if (!found) { tmp_array[j] = global_id; tmp_array[j + 1] = call_count; j += 2; } } /* Now sort the temp array. */ gcov_sort_n_vals (tmp_array, j); /* Now copy back the top half of the temp array. */ for (k = 0; k < GCOV_ICALL_TOPN_NCOUNTS - 1; k += 2) { value_array[k] = tmp_array[k]; value_array[k + 1] = tmp_array[k + 1]; } } } /* Time profiles are merged so that minimum from all valid (greater than zero) is stored. There could be a fork that creates new counters. To have the profile stable, we chosen to pick the smallest function visit time. */ void __gcov_dyn_ipa_merge_time_profile (gcov_type *dest, gcov_type *src, unsigned n_counters) { unsigned i; gcov_type value; for (i = 0; i < n_counters; i++) { value = src[i]; if (value && (!dest[i] || value < dest[i])) dest[i] = value; } } /* The profile merging function that just merges N_COUNTERS most common value counters from array SRC to those in DEST. Adapted from __gcov_merge_single. */ void __gcov_dyn_ipa_merge_single (gcov_type *dest, gcov_type *src, unsigned n_counters) { unsigned i, n_measures; gcov_type value, counter, all; gcc_assert (!(n_counters % 3)); n_measures = n_counters / 3; for (i = 0; i < n_measures; i++, dest += 3, src += 3) { value = src[0]; counter = src[1]; all = src[2]; if (dest[0] == value) dest[1] += counter; else if (counter > dest[1]) { dest[0] = value; dest[1] = counter - dest[1]; } else dest[1] -= counter; dest[2] += all; } } /* The profile merging function that just merges N_COUNTERS most common difference counters from array SRC to those in DEST. Adapted from __gcov_merge_delta. */ void __gcov_dyn_ipa_merge_delta (gcov_type *dest, gcov_type *src, unsigned n_counters) { unsigned i, n_measures; gcov_type value, counter, all; gcc_assert (!(n_counters % 4)); n_measures = n_counters / 4; for (i = 0; i < n_measures; i++, dest += 4, src += 4) { value = src[1]; counter = src[2]; all = src[3]; if (dest[1] == value) dest[2] += counter; else if (counter > dest[2]) { dest[1] = value; dest[2] = counter - dest[2]; } else dest[2] -= counter; dest[3] += all; } } /* Type of function used to merge counters. */ typedef void (*gcov_dyn_ipa_merge_fn) (gcov_type *, gcov_type *, gcov_unsigned_t); /* Merge functions for counters. */ #define DEF_GCOV_COUNTER(COUNTER, NAME, FN_TYPE) __gcov_dyn_ipa_merge ## FN_TYPE, static gcov_dyn_ipa_merge_fn ctr_merge_functions[GCOV_COUNTERS] = { #include "gcov-counter.def" }; #undef DEF_GCOV_COUNTER #if 0 static gcov_dyn_ipa_merge_fn ctr_merge_functions[GCOV_COUNTERS] = { __gcov_dyn_ipa_merge_add, __gcov_dyn_ipa_merge_add, __gcov_dyn_ipa_merge_add, __gcov_dyn_ipa_merge_single, __gcov_dyn_ipa_merge_delta, __gcov_dyn_ipa_merge_single, __gcov_dyn_ipa_merge_add, __gcov_dyn_ipa_merge_ior, __gcov_dyn_ipa_merge_icall_topn, __gcov_dyn_ipa_merge_dc, }; #endif /* Copy counters from SRC_CTRS array to DEST_CTRS array, where SRC_CTRS is indexed by the GCOV_COUNTER type, and DEST_CTRS is an array holding only the mergable counters to emit to the gcda file for DEST_GUID. */ static void copy_ctrs (const struct gcov_ctr_info *dest_ctrs, gcov_type dest_guid, const struct gcov_ctr_info *src_ctrs) { unsigned dest_mod_id = get_module_ident_from_func_glob_uid (dest_guid); struct gcov_info *dest_mod_info = the_dyn_call_graph.modules[dest_mod_id - 1]; int i; for (i = 0; i < GCOV_COUNTERS; i++) { if (!dest_mod_info->merge[i]) continue; gcov_unsigned_t num = dest_ctrs->num; // This could be different if code was optimized differently // (e.g. early-inlined in some modules but not others). // If they are different then just punt on merge of this counter // (what about other counters?). //gcc_assert (dest_ctrs[i].num == num); if (num && src_ctrs[i].num == num) (*ctr_merge_functions[i]) (dest_ctrs->values, src_ctrs[i].values, num); dest_ctrs++; } } /* Merge counters from SRC_CTRS array to DEST_CTRS array, where DEST_CTRS is indexed by the GCOV_COUNTER type, and SRC_CTRS is an array holding only the mergable counters from the gcda file for SRC_GUID. */ static void merge_ctrs (struct gcov_ctr_info *dest_ctrs, const struct gcov_ctr_info *src_ctrs, gcov_type src_guid) { unsigned src_mod_id = get_module_ident_from_func_glob_uid (src_guid); struct gcov_info *src_mod_info = the_dyn_call_graph.modules[src_mod_id - 1]; unsigned i, j; for (i = 0; i < GCOV_COUNTERS; i++) { if (!src_mod_info->merge[i]) continue; gcov_unsigned_t num = src_ctrs->num; // This could be different if code was optimized differently // (e.g. call counters when ipa-inlined in some modules but not others?). // If they are different then just punt on merge of this counter // (what about other counters?). //gcc_assert (dest_ctrs[i].num == num); if (num) { /* If this is the first source counter array containing counters for this counter type, allocate the associated number of counter values in the dest counter array. */ if (!dest_ctrs[i].num) { dest_ctrs[i].values = XNEWVEC (gcov_type, num); for (j = 0; j < num; j++) dest_ctrs[i].values[j] = 0; dest_ctrs[i].num = num; } if (dest_ctrs[i].num == num) (*ctr_merge_functions[i]) (dest_ctrs[i].values, src_ctrs->values, num); } src_ctrs++; } } /* Walks the set of functions that have the same lineno and cfg checksum, and 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 struct checksum_alias_info *info, int *changed) { /* See if there are any zero count functions to fix. */ int found = 0; struct checksum_alias *alias; for (alias = info->alias_list; alias; alias = alias->next_alias) { if (alias->zero_count_fixup) { found = 1; break; } } if (!found) return 1; /* 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 = info->alias_list; alias; alias = alias->next_alias) { if (alias->zero_count_fixup) continue; merge_ctrs (merged_ctrs, alias->fi_ptr->ctrs, alias->guid); found = 1; } /* Check if we found a non-zero count function to fix up from. */ if (!found) return 1; /* At this point we know we have a zero count function to fixup, and data from which to fix it up. */ *changed = 1; /* Walk them again and copy the merged counters into 0-count copies. */ for (alias = info->alias_list; alias; alias = alias->next_alias) { if (!alias->zero_count_fixup) continue; copy_ctrs (alias->fi_ptr->ctrs, alias->guid, merged_ctrs); *alias->zero_count_fixup = 1; } return 1; } /* Walks the set of functions that have the same lineno_checksum, and performs counter merging for functions that have the same cfg_checksum as well. VALUE contains the lineno_checksum_alias structure for a given lineno_checksum, and DATA1 contains a pointer to a flag that should be set to 1 if any fixups were applied. */ static int gcov_fixup_counters_lineno (const void *value, void *data1, void *data2 ATTRIBUTE_UNUSED, void *data3 ATTRIBUTE_UNUSED) { const struct lineno_checksum_alias *a = (const struct lineno_checksum_alias*) value; int *changed = (int *) data1; 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; } /* Routine to perform counter fixup for COMDAT functions with missing counters. Returns 1 if any updates were performed, 0 otherwise. Walks the sets of functions having the same lineno and cfg checksums and merges all non-zero counters, copying the merged counters into any copies with all-zero counts. This is done because the linker will chose one out-of-line copy of a COMDAT, and only that copy will get non-zero counters. Other copies that were IPA inlined may have non-zero counts, which we don't overwrite as they contain more context-sensitive data. */ static int gcov_fixup_zero_counters (void) { int changed = 0; pointer_set_traverse (the_dyn_call_graph.lineno_pointer_sets, gcov_fixup_counters_lineno, &changed, 0, 0); return changed; } /* Compute module groups needed for L-IPO compilation. The ZERO_COUNTS flags are set for functions with zero count fixups applied. Returns 1 if any counter fixups were applied, requiring a profile rewrite, 0 otherwise. */ int __gcov_compute_module_groups (char **zero_counts) { gcov_type cut_off_count; char *seed = getenv ("LIPO_RANDOM_GROUPING"); char *max_group_size = seed ? strchr (seed, ':') : 0; /* The random group is set via compile time parameter. */ if (__gcov_lipo_random_group_size != 0) { srand (__gcov_lipo_random_seed); init_dyn_call_graph (); gcov_compute_random_module_groups (__gcov_lipo_random_group_size); if (do_cgraph_dump () != 0) { fprintf (stderr, " Creating random grouping with %u:%u\n", __gcov_lipo_random_seed, __gcov_lipo_random_group_size); } return 0; } else if (seed && max_group_size) { *max_group_size = '\0'; max_group_size++; srand (atoi (seed)); init_dyn_call_graph (); gcov_compute_random_module_groups (atoi (max_group_size)); if (do_cgraph_dump () != 0) { fprintf (stderr, " Creating random grouping with %s:%s\n", seed, max_group_size); } return 0; } if (flag_use_existing_grouping) { read_modu_groups_from_imports_files (); 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 (zero_counts); cut_off_count = gcov_compute_cutoff_count (); gcov_compute_module_groups (cut_off_count); gcov_dump_callgraph (cut_off_count); int changed = 0; if (fixup_type & 0x2) changed |= gcov_fixup_zero_counters (); if (fixup_type & 0x1) changed |= gcov_fixup_icall_profile (); return changed; } /* Dumper function for NODE. */ static void gcov_dump_cgraph_node_short (struct dyn_cgraph_node *node) { unsigned mod_id, func_id; struct gcov_info *mod_info; mod_id = get_module_ident_from_func_glob_uid (node->guid); func_id = get_intra_module_func_id (node->guid); mod_info = the_dyn_call_graph.modules[mod_id - 1]; fprintf (stderr, "NODE(%llx) module(%s) func(%u)", (long long)node->guid, mod_info->mod_info->source_filename, func_id); } /* Dumper function for NODE. M is the module id and F is the function id. */ static void gcov_dump_cgraph_node (struct dyn_cgraph_node *node, unsigned m, unsigned f) { unsigned mod_id, func_id; struct gcov_info *mod_info; struct dyn_cgraph_edge *callers; struct dyn_cgraph_edge *callees; mod_id = get_module_ident_from_func_glob_uid (node->guid); func_id = get_intra_module_func_id (node->guid); gcc_assert (mod_id == (m + 1) && func_id == f); mod_info = the_dyn_call_graph.modules[mod_id - 1]; fprintf (stderr, "NODE(%llx) module(%s) func(%x)\n", (long long) node->guid, mod_info->mod_info->source_filename, f); /* Now dump callers. */ callers = node->callers; fprintf (stderr, "\t[CALLERS]\n"); while (callers != 0) { fprintf (stderr,"\t\t[count=%ld] ", (long) callers->count); gcov_dump_cgraph_node_short (callers->caller); fprintf (stderr,"\n"); callers = callers->next_caller; } callees = node->callees; fprintf (stderr, "\t[CALLEES]\n"); while (callees != 0) { fprintf (stderr,"\t\t[count=%ld] ", (long) callees->count); gcov_dump_cgraph_node_short (callees->callee); fprintf (stderr,"\n"); callees = callees->next_callee; } } /* Dumper function for NODE. M is the module_ident -1 and F is the function id. */ static void gcov_dump_cgraph_node_dot (struct dyn_cgraph_node *node, unsigned m, unsigned f, gcov_type cutoff_count) { unsigned mod_id, func_id, imp_len = 0, i; struct gcov_info *mod_info; const struct dyn_imp_mod **imp_mods; struct dyn_cgraph_edge *callees; mod_id = get_module_ident_from_func_glob_uid (node->guid); func_id = get_intra_module_func_id (node->guid); gcc_assert (mod_id == (m + 1) && func_id == f); mod_info = the_dyn_call_graph.modules[mod_id - 1]; fprintf (stderr, "NODE_%llx[label=\"MODULE\\n(%s)\\n FUNC(%x)\\n", (long long) node->guid, mod_info->mod_info->source_filename, f); imp_mods = gcov_get_sorted_import_module_array (mod_info, &imp_len); fprintf (stderr, "IMPORTS:\\n"); if (imp_mods) { for (i = 0; i < imp_len; i++) fprintf (stderr, "%s\\n", imp_mods[i]->imp_mod->mod_info->source_filename); fprintf (stderr, "\"]\n"); free (imp_mods); } else fprintf (stderr, "\"]\n"); callees = node->callees; while (callees != 0) { if (callees->count >= cutoff_count) fprintf (stderr, "NODE_%llx -> NODE_%llx[label=%lld color=red]\n", (long long) node->guid, (long long) callees->callee->guid, (long long) callees->count); else fprintf (stderr, "NODE_%llx -> NODE_%llx[label=%lld color=blue]\n", (long long) node->guid, (long long) callees->callee->guid, (long long) callees->count); callees = callees->next_callee; } } /* Dump dynamic call graph. CUTOFF_COUNT is the computed hot edge threshold. */ static void gcov_dump_callgraph (gcov_type cutoff_count) { struct gcov_info *gi_ptr; unsigned m_ix; int do_dump; do_dump = do_cgraph_dump (); if (do_dump == 0) return; fprintf (stderr,"digraph dyn_call_graph {\n"); fprintf (stderr,"node[shape=box]\nsize=\"11,8.5\"\n"); for (m_ix = 0; m_ix < the_dyn_call_graph.num_modules; m_ix++) { const struct gcov_fn_info *fi_ptr; unsigned f_ix; gi_ptr = the_dyn_call_graph.modules[m_ix]; if (gi_ptr == NULL) continue; for (f_ix = 0; f_ix < gi_ptr->n_functions; f_ix++) { struct dyn_cgraph_node *node; fi_ptr = gi_ptr->functions[f_ix]; node = (struct dyn_cgraph_node *) *(pointer_set_find_or_insert (the_dyn_call_graph.call_graph_nodes[m_ix], fi_ptr->ident)); gcc_assert (node); /* skip dead functions */ if (!node->callees && !node->callers) continue; if (do_dump == 1) gcov_dump_cgraph_node (node, m_ix, fi_ptr->ident); else gcov_dump_cgraph_node_dot (node, m_ix, fi_ptr->ident, cutoff_count); } } fprintf (stderr,"}\n"); } static int dump_imported_modules_1 (const void *value, void *data1 ATTRIBUTE_UNUSED, void *data2 ATTRIBUTE_UNUSED, void *data3 ATTRIBUTE_UNUSED) { const struct dyn_imp_mod *d = (const struct dyn_imp_mod*) value; fprintf (stderr, "%d ", get_module_ident (d->imp_mod)); return 1; } static int dump_exported_to_1 (const void *value, void *data1 ATTRIBUTE_UNUSED, void *data2 ATTRIBUTE_UNUSED, void *data3 ATTRIBUTE_UNUSED) { const struct gcov_info *modu = (const struct gcov_info *) value; fprintf (stderr, "%d ", get_module_ident (modu)); return 1; } static void ATTRIBUTE_UNUSED debug_dump_imported_modules (const struct dyn_pointer_set *p) { fprintf (stderr, "imported: "); pointer_set_traverse (p, dump_imported_modules_1, 0, 0, 0); fprintf (stderr, "\n"); } static void ATTRIBUTE_UNUSED debug_dump_exported_to (const struct dyn_pointer_set *p) { fprintf (stderr, "exported: "); pointer_set_traverse (p, dump_exported_to_1, 0, 0, 0); fprintf (stderr, "\n"); } #endif