diff options
Diffstat (limited to 'gcc-4.9/libgcc/dyn-ipa.c')
-rw-r--r-- | gcc-4.9/libgcc/dyn-ipa.c | 2540 |
1 files changed, 2540 insertions, 0 deletions
diff --git a/gcc-4.9/libgcc/dyn-ipa.c b/gcc-4.9/libgcc/dyn-ipa.c new file mode 100644 index 000000000..eb5ae9cc9 --- /dev/null +++ b/gcc-4.9/libgcc/dyn-ipa.c @@ -0,0 +1,2540 @@ +/* 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 +<http://www.gnu.org/licenses/>. */ + +#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; +}; + +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; +}; + +/* 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_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 (void) {} +#else + +void __gcov_compute_module_groups (void) 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; + +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; + +/* 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); +} + +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); + + 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. */ + +static void +gcov_add_cgraph_edge (struct dyn_cgraph_node *caller, + struct dyn_cgraph_node *callee, + gcov_type count) +{ + 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; + + 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); + } +} + +/* 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); + } + } +} + +/* Build the dynamic call graph. */ + +static void +gcov_build_callgraph (void) +{ + 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 && 0) + { + 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++; + } + 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; + + 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); + } +} + +/* 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, j; + 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; + for (i = 0; i < num_strings; i++) + { + gcov_unsigned_t string_len + = (strlen (module_info->string_array[i]) + sizeof (gcov_unsigned_t)) + / sizeof (gcov_unsigned_t); + len += string_len; + len += 1; /* Each string is lead by a length. */ + } + + 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. */ + for (j = 0; j < num_strings; j++) + { + gcov_unsigned_t *aligned_string; + gcov_unsigned_t string_len = + (strlen (module_info->string_array[j]) + sizeof (gcov_unsigned_t)) / + sizeof (gcov_unsigned_t); + aligned_string = (gcov_unsigned_t *) + alloca ((string_len + 1) * sizeof (gcov_unsigned_t)); + memset (aligned_string, 0, (string_len + 1) * sizeof (gcov_unsigned_t)); + aligned_string[0] = string_len; + strcpy ((char*) (aligned_string + 1), module_info->string_array[j]); + for (i = 0; i < (string_len + 1); i++) + gcov_write_unsigned (aligned_string[i]); + } +} + +/* 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; + + 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 */ +} + +/* Compute module groups needed for L-IPO compilation. */ + +void +__gcov_compute_module_groups (void) +{ + 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; + } + 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; + } + + if (flag_use_existing_grouping) + { + read_modu_groups_from_imports_files (); + return; + } + + /* First compute dynamic call graph. */ + gcov_build_callgraph (); + + cut_off_count = gcov_compute_cutoff_count (); + + gcov_compute_module_groups (cut_off_count); + + gcov_dump_callgraph (cut_off_count); + +} + +/* 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 |