[google gcc-4_7] new module grouping method (issue7393058)
Rong Xu
xur@google.com
Mon Feb 25 19:19:00 GMT 2013
Hi,
This is the patch that implements a new module grouping.
It's based on module level graph and simple inclusion based algorithm.
Tests are ongoing with google internal benchmarks and spec2k, spec2k6.
Thanks,
-Rong
2013-02-25 Rong Xu <xur@google.com>
* libgcc/dyn-ipa.c (struct dyn_cgraph): New Decls.
(struct modu_edge): Ditto.
(get_module_id_value): New function for new module gruouping impl.
(get_cgraph_node): Ditto.
(gcov_info_get_key): Ditto.
(get_exported_to): Ditto.
(create_exported_to): Ditto.
(get_imported_modus): Ditto.
(pointer_set_destroy_2): Ditto.
(pointer_set_contains): Ditto.
(dyn_fibheap_new): Fibheap impl.
(fibnode_new): Ditto.
(dyn_fibheap_compare): Ditto.
(dyn_fibheap_comp_data): Ditto.
(dyn_fibheap_insert): Ditto.
(dyn_fibheap_extract_min): Ditto.
(dyn_fibheap_delete): Ditto.
(dyn_fibheap_empty): Ditto.
(dyn_fibheap_extr_min_node): Ditto.
(dyn_fibheap_ins_root): Ditto.
(dyn_fibheap_rem_root): Ditto.
(dyn_fibheap_consolidate): Ditto.
(dyn_fibheap_link): Ditto.
(fibnode_insert_after): Ditto.
(fibnode_remove): Ditto.
(init_dyn_call_graph): Support new module grouping impl.
(__gcov_finalize_dyn_callgraph): Ditto.
(gcov_compute_module_groups): Ditto.
(modu_graph_add_edge): Ditto.
(modu_graph_process_dyn_cgraph_node): Ditto.
(build_modu_graph): Ditto.
(collect_ggc_mem_size): Ditto.
(get_group_ggc_mem): Ditto.
(modu_union_ggc_size): Ditto.
(modu_add_auxiliary_1): Ditto.
(modu_add_auxiliary): Ditto.
(ps_check_ggc_mem): Ditto.
(ps_add_auxiliary): Ditto.
(modu_edge_add_auxiliary): Ditto.
(compute_module_group_groups_1_impl): Ditto.
(gcov_compute_module_groups_1): Ditto.
(gcov_compute_module_groups_0): Ditto.
(gcov_write_module_info): Ditto.
(gcov_write_module_infos_0):Ditto.
(gcov_write_module_infos_1):Ditto.
(gcov_write_module_infos): Ditto.
(gcov_dump_cgraph_node_short): Ditto.
(gcov_dump_callgraph): Ditto.
(dump_imported_modules_1): Ditto.
(dump_exported_to_1): Ditto.
(debug_dump_imported_modules): Ditto.
(debug_dump_exported_to): Ditto.
* gcc/c-family/c-opts.c (c_common_parse_file): not check ggc_memory
in the new module gruping impl.
* gcc/gcov-io.c (gcov_read_module_info): Change is_exported_to to flag.
* gcc/gcov-io.h (struct gcov_module_info): Ditto.
* gcc/gcov-dump.c (tag_module_info): Ditto.
* gcc/l-ipo.h: Ditto.
* gcc/auto-profile.c (afdo_add_module): Ditto.
* gcc/coverage.c (read_counts_file): Ditto.
(build_gcov_module_info_type):Ditto.
(build_gcov_module_info_value):Ditto.
(add_module_info):Ditto.
* gcc/toplev.c: New decl.
Index: gcc/c-family/c-opts.c
===================================================================
--- gcc/c-family/c-opts.c (revision 196161)
+++ gcc/c-family/c-opts.c (working copy)
@@ -1167,7 +1167,7 @@ c_common_parse_file (void)
to hit memory limits, and cause thrashing -- prevent this by not
processing any further auxiliary modules if we reach a certain
memory limit. */
- if (lipo_max_mem_reached (i))
+ if (!include_all_aux && lipo_max_mem_reached (i))
num_in_fnames = i + 1;
pop_file_scope ();
/* And end the main input file, if the debug writer wants it */
Index: gcc/toplev.c
===================================================================
--- gcc/toplev.c (revision 196161)
+++ gcc/toplev.c (working copy)
@@ -203,6 +203,10 @@ unsigned primary_module_id = 0;
unsigned current_module_id = 0;
+/* Include all auxiliary modules specified in the profile. This
+ will bypass the ggc_memory limit check. */
+bool include_all_aux = 0;
+
/* Initialize src_pwd with the given string, and return true. If it
was already initialized, return false. As a special case, it may
be called with a NULL argument to test whether src_pwd has NOT been
Index: gcc/auto-profile.c
===================================================================
--- gcc/auto-profile.c (revision 196161)
+++ gcc/auto-profile.c (working copy)
@@ -442,7 +442,7 @@ afdo_add_module (struct gcov_module_info **module_
*module_info = XCNEWVAR (struct gcov_module_info, info_sz);
(*module_info)->ident = module->ident;
(*module_info)->is_primary = is_primary;
- (*module_info)->is_exported = is_primary ? module->exported : 1;
+ (*module_info)->flag = is_primary ? module->exported : 1;
(*module_info)->source_filename = module->name;
(*module_info)->num_quote_paths = module->num_quote_paths;
(*module_info)->num_bracket_paths = module->num_bracket_paths;
Index: gcc/gcov-dump.c
===================================================================
--- gcc/gcov-dump.c (revision 196161)
+++ gcc/gcov-dump.c (working copy)
@@ -578,10 +578,15 @@ tag_module_info (const char *filename ATTRIBUTE_UN
}
else
{
- const char *suffix = mod_info->is_primary
- ? (mod_info->is_exported ? "primary, exported" : "primary")
- : "auxiliary";
- printf (": %s [%s]", mod_info->source_filename, suffix);
+ const char *primary_suffix = mod_info->is_primary ? "primary" : "";
+ const char *export_suffix = MODULE_EXPORTED_FLAG (mod_info)
+ ? mod_info->is_primary ? "exported" : "auxiliary"
+ : "";
+ const char *include_all_suffix = mod_info->is_primary
+ ? MODULE_INCLUDE_ALL_AUX_FLAG (mod_info) ? "include_all" : ""
+ : "";
+ printf (": %s [%s %s %s]", mod_info->source_filename,
+ primary_suffix, export_suffix, include_all_suffix);
}
}
Index: gcc/l-ipo.h
===================================================================
--- gcc/l-ipo.h (revision 196161)
+++ gcc/l-ipo.h (working copy)
@@ -44,6 +44,7 @@ extern unsigned primary_module_id;
/* Current module id. */
extern unsigned current_module_id;
+extern unsigned include_all_aux;
extern struct gcov_module_info **module_infos;
extern int is_last_module (unsigned mod_id);
Index: gcc/coverage.c
===================================================================
--- gcc/coverage.c (revision 196161)
+++ gcc/coverage.c (working copy)
@@ -889,6 +889,7 @@ read_counts_file (const char *da_file_name, unsign
modset = pointer_set_create ();
pointer_set_insert (modset, (void *)(size_t)mod_info->ident);
primary_module_id = mod_info->ident;
+ include_all_aux = MODULE_INCLUDE_ALL_AUX_FLAG (mod_info);
module_infos = XCNEWVEC (struct gcov_module_info *, 1);
module_infos[0] = XCNEWVAR (struct gcov_module_info, info_sz);
memcpy (module_infos[0], mod_info, info_sz);
@@ -963,9 +964,11 @@ read_counts_file (const char *da_file_name, unsign
{
inform (input_location,
"MODULE Id=%d, Is_Primary=%s,"
- " Is_Exported=%s, Name=%s (%s)",
+ " Is_Exported=%s, Include_all=%s, Name=%s (%s)",
mod_info->ident, mod_info->is_primary?"yes":"no",
- mod_info->is_exported?"yes":"no", mod_info->source_filename,
+ MODULE_EXPORTED_FLAG (mod_info)?"yes":"no",
+ MODULE_INCLUDE_ALL_AUX_FLAG (mod_info)?"yes":"no",
+ mod_info->source_filename,
mod_info->da_filename);
}
}
@@ -2109,7 +2112,7 @@ build_gcov_module_info_type (void)
DECL_CHAIN (field) = fields;
fields = field;
- /* is_exported */
+ /* flag: is_exported and include_all_aux flag. */
field = build_decl (BUILTINS_LOCATION, FIELD_DECL,
NULL_TREE, get_gcov_unsigned_t ());
DECL_CHAIN (field) = fields;
@@ -2232,7 +2235,7 @@ build_gcov_module_info_value (tree mod_type)
flag_dyn_ipa ? 1 : 0));
info_fields = DECL_CHAIN (info_fields);
- /* is_exported */
+ /* flag */
CONSTRUCTOR_APPEND_ELT (v, info_fields,
build_int_cstu (get_gcov_unsigned_t (), 0));
info_fields = DECL_CHAIN (info_fields);
@@ -2656,7 +2659,7 @@ add_module_info (unsigned module_id, bool is_prima
module_infos[index] = XNEW (struct gcov_module_info);
cur_info = module_infos[index];
cur_info->ident = module_id;
- cur_info->is_exported = true;
+ SET_MODULE_EXPORTED (cur_info);
cur_info->num_quote_paths = 0;
cur_info->num_bracket_paths = 0;
cur_info->da_filename = NULL;
Index: gcc/gcov-io.c
===================================================================
--- gcc/gcov-io.c (revision 196161)
+++ gcc/gcov-io.c (working copy)
@@ -746,7 +746,7 @@ gcov_read_module_info (struct gcov_module_info *mo
gcov_unsigned_t src_filename_len, filename_len, i, j, num_strings;
mod_info->ident = gcov_read_unsigned ();
mod_info->is_primary = gcov_read_unsigned ();
- mod_info->is_exported = gcov_read_unsigned ();
+ mod_info->flag = gcov_read_unsigned ();
mod_info->lang = gcov_read_unsigned ();
mod_info->num_quote_paths = gcov_read_unsigned ();
mod_info->num_bracket_paths = gcov_read_unsigned ();
Index: gcc/gcov-io.h
===================================================================
--- gcc/gcov-io.h (revision 196161)
+++ gcc/gcov-io.h (working copy)
@@ -638,7 +638,9 @@ struct gcov_module_info
(1) means FDO/LIPO in instrumented binary.
(2) means IS_PRIMARY in persistent file or
memory copy used in profile-use. */
- gcov_unsigned_t is_exported;
+ gcov_unsigned_t flag; /* bit 0: is_exported,
+ bit 1: need to include all the auxiliary
+ modules in use compilation. */
gcov_unsigned_t lang; /* lower 16 bits encode the language, and the upper
16 bits enocde other attributes, such as whether
any assembler is present in the source, etc. */
@@ -655,8 +657,12 @@ struct gcov_module_info
extern struct gcov_module_info **module_infos;
extern unsigned primary_module_id;
+#define SET_MODULE_INCLUDE_ALL_AUX(modu) ((modu->flag |= 0x2))
+#define MODULE_INCLUDE_ALL_AUX_FLAG(modu) ((modu->flag & 0x2))
+#define SET_MODULE_EXPORTED(modu) ((modu->flag |= 0x1))
+#define MODULE_EXPORTED_FLAG(modu) ((modu->flag & 0x1))
#define PRIMARY_MODULE_EXPORTED \
- (module_infos[0]->is_exported \
+ (MODULE_EXPORTED_FLAG (module_infos[0]) \
&& !((module_infos[0]->lang & GCOV_MODULE_ASM_STMTS) \
&& flag_ripa_disallow_asm_modules))
Index: libgcc/dyn-ipa.c
===================================================================
--- libgcc/dyn-ipa.c (revision 196161)
+++ libgcc/dyn-ipa.c (working copy)
@@ -73,6 +73,12 @@ struct dyn_module_info
{
struct dyn_pointer_set *imported_modules;
gcov_unsigned_t max_func_ident;
+
+ /* Used by new algo. 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
@@ -83,8 +89,30 @@ struct dyn_cgraph
struct dyn_module_info *sup_modules;
unsigned num_modules;
unsigned num_nodes_executed;
+ /* used by new_alg */
+ 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;
+ unsigned char visited; /* needed? */
+};
+
+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 combined edges */
+ gcov_type sum_count;
+ unsigned char visited; /* needed? */
+};
+
struct dyn_pointer_set
{
size_t log_slots;
@@ -95,6 +123,32 @@ struct dyn_pointer_set
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 int dyn_fibheap_empty (dyn_fibheap_t);
+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;
@@ -112,7 +166,7 @@ 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 int do_cgraph_dump (void);
static void
gcov_dump_cgraph_node_dot (struct dyn_cgraph_node *node,
@@ -120,6 +174,8 @@ gcov_dump_cgraph_node_dot (struct dyn_cgraph_node
gcov_type cutoff_count);
static void
pointer_set_destroy (struct dyn_pointer_set *pset);
+static void
+pointer_set_destroy_2 (struct dyn_pointer_set *pset);
static void **
pointer_set_find_or_insert (struct dyn_pointer_set *pset, unsigned key);
static struct dyn_pointer_set *
@@ -129,6 +185,14 @@ static struct dyn_cgraph the_dyn_call_graph;
static int total_zero_count = 0;
static int total_insane_count = 0;
+static int flag_alg_mode = 1;
+static int flag_modu_merge_edges = 1;
+#if 0
+static gcov_unsigned_t mem_threshold = 3500000;
+#else
+static gcov_unsigned_t mem_threshold = 2800000;
+#endif
+
/* Returns 0 if no dump is enabled. Returns 1 if text form graph
dump is enabled. Returns 2 if .dot form dump is enabled. */
@@ -144,7 +208,7 @@ do_cgraph_dump (void)
if (!dyn_cgraph_dump || !strlen (dyn_cgraph_dump))
return 0;
-
+
if (dyn_cgraph_dump[0] == '1')
return 1;
if (dyn_cgraph_dump[0] == '2')
@@ -179,6 +243,14 @@ get_module_idx (const struct gcov_info *module_inf
return module_info->mod_info->ident - 1;
}
+/* Return module_id for MODULE_INFO. */
+
+static inline gcov_unsigned_t
+get_module_id_value (const struct gcov_info *module_info)
+{
+ return module_info->mod_info->ident;
+}
+
/* Return intra-module function id given function global unique id
FUNC_GUID. */
@@ -212,6 +284,33 @@ get_cgraph_node (gcov_type func_guid)
(the_dyn_call_graph.call_graph_nodes[mod_id], 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_id_value (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 *
@@ -228,6 +327,52 @@ 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_id_value ((const struct gcov_info *)p);
+}
+
+static struct dyn_pointer_set *
+get_exported_to (unsigned m_ix)
+{
+ gcc_assert (m_ix != 0);
+ return the_dyn_call_graph.sup_modules[m_ix-1].exported_to;
+}
+
+static struct dyn_pointer_set *
+create_exported_to (unsigned m_ix)
+{
+ struct dyn_pointer_set *p;
+
+ gcc_assert (m_ix != 0);
+ the_dyn_call_graph.sup_modules[m_ix-1].exported_to = p
+ = pointer_set_create (gcov_info_get_key);
+ return p;
+}
+
+static struct dyn_pointer_set *
+get_imported_modus (unsigned m_ix)
+{
+ struct dyn_pointer_set *p;
+ struct gcov_info *gi_ptr;
+
+ gcc_assert (m_ix != 0);
+ p = the_dyn_call_graph.sup_modules[m_ix-1].imported_modules;
+
+ if (p)
+ return p;
+
+ the_dyn_call_graph.sup_modules[m_ix-1].imported_modules = p
+ = pointer_set_create (imp_mod_get_key);
+
+ gi_ptr = the_dyn_call_graph.modules[m_ix-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
@@ -235,6 +380,7 @@ init_dyn_call_graph (void)
{
unsigned num_modules = 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;
@@ -261,6 +407,16 @@ init_dyn_call_graph (void)
gi_ptr = __gcov_list;
+ if ((env_str = getenv ("GCOV_DYN_ALG")))
+ {
+ flag_alg_mode = atoi (env_str);
+
+ flag_modu_merge_edges = (getenv ("GDOV_DYN_MERGE_EDGES") != 0);
+ if (do_dump)
+ fprintf (stderr, "!!!! Using ALG=%d merge_edges=%d. \n",
+ flag_alg_mode, flag_modu_merge_edges);
+ }
+
if (do_dump)
fprintf (stderr, "Group mem limit: %u KB \n",
__gcov_lipo_max_mem);
@@ -271,8 +427,9 @@ init_dyn_call_graph (void)
struct dyn_cgraph_node *node;
if (do_dump)
- fprintf (stderr, "Module %s uses %u KB memory in parsing\n",
+ fprintf (stderr, "Module %s %d uses %u KB memory in parsing\n",
gi_ptr->mod_info->source_filename,
+ get_module_id_value (gi_ptr),
gi_ptr->mod_info->ggc_memory);
mod_id = get_module_idx (gi_ptr);
@@ -296,6 +453,15 @@ init_dyn_call_graph (void)
max_func_ident = fi_ptr->ident;
}
the_dyn_call_graph.sup_modules[mod_id].max_func_ident = max_func_ident;
+ if (flag_alg_mode == 1)
+ {
+ struct dyn_module_info *sup_module =
+ &(the_dyn_call_graph.sup_modules[mod_id]);
+
+ sup_module->group_ggc_mem = gi_ptr->mod_info->ggc_memory;
+ sup_module->imported_modules = 0;
+ sup_module->exported_to = 0;
+ }
}
}
@@ -338,6 +504,8 @@ __gcov_finalize_dyn_callgraph (void)
/* 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 == 1 && the_dyn_call_graph.sup_modules[i].exported_to)
+ pointer_set_destroy_2 (the_dyn_call_graph.sup_modules[i].exported_to);
}
XDELETEVEC (the_dyn_call_graph.call_graph_nodes);
XDELETEVEC (the_dyn_call_graph.sup_modules);
@@ -555,6 +723,15 @@ pointer_set_destroy (struct dyn_pointer_set *pset)
XDELETE (pset);
}
+/* Reclaim the memory of PSET but not the value pointer. */
+static void
+pointer_set_destroy_2 (struct dyn_pointer_set *pset)
+{
+ size_t i;
+ 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
@@ -614,6 +791,7 @@ pointer_set_find_or_insert (struct dyn_pointer_set
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. */
@@ -628,31 +806,35 @@ pointer_set_traverse (const struct dyn_pointer_set
break;
}
+
+/* Returns nonzero if PSET contains P. P must be nonnull.
+ Collisions are resolved by linear probing. */
+
static int
-imp_mod_set_insert (struct dyn_pointer_set *p, const struct gcov_info *imp_mod,
- double wt)
+pointer_set_contains (const struct dyn_pointer_set *pset, unsigned key)
{
- struct dyn_imp_mod **m = (struct dyn_imp_mod **)
- pointer_set_find_or_insert (p, imp_mod->mod_info->ident);
- if (*m)
+ size_t n = hash1 (key, pset->n_slots, pset->log_slots);
+
+ while (1)
{
- (*m)->weight += wt;
- return 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;
+ }
}
- else
- {
- *m = XNEW (struct dyn_imp_mod);
- (*m)->imp_mod = imp_mod;
- (*m)->weight = wt;
- p->n_elements++;
- return 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)
@@ -817,12 +999,6 @@ gcov_compute_cutoff_count (void)
return cutoff_count;
}
-static inline unsigned
-imp_mod_get_key (const void *p)
-{
- return ((const struct dyn_imp_mod *) p)->imp_mod->mod_info->ident;
-}
-
/* Return the imported module set for NODE. */
static struct dyn_pointer_set *
@@ -856,7 +1032,7 @@ gcov_mark_export_modules (const void *value,
const struct gcov_info *module_info
= ((const struct dyn_imp_mod *) value)->imp_mod;
- module_info->mod_info->is_exported = 1;
+ SET_MODULE_EXPORTED (module_info->mod_info);
return 1;
}
@@ -1065,14 +1241,652 @@ gcov_process_cgraph_node (struct dyn_cgraph_node *
}
}
+static void gcov_compute_module_groups_0 (gcov_type cutoff_count);
+static void gcov_compute_module_groups_1 (gcov_type cutoff_count);
+
+/* 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. */
+dyn_fibheap_t
+dyn_fibheap_new (void)
+{
+ return (dyn_fibheap_t) calloc (1, sizeof (struct dyn_fibheap));
+}
+
+/* Create a new fibonacci heap node. */
+static fibnode_t
+fibnode_new (void)
+{
+ fibnode_t node;
+
+ node = (fibnode_t) calloc (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. */
+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. */
+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);
+}
+
+/* Determine if HEAP is empty. */
+int
+dyn_fibheap_empty (dyn_fibheap_t heap)
+{
+ return heap->nodes == 0;
+}
+
+/* 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 1:
+ return gcov_compute_module_groups_1 (cutoff_count);
+ case 0:
+ default:
+ return gcov_compute_module_groups_0 (cutoff_count);
+ }
+}
+
+static void
+modu_graph_add_edge (unsigned m_ix, unsigned callee_m_ix, gcov_type count)
+{
+ struct modu_node *mnode = &the_dyn_call_graph.modu_nodes[m_ix];
+ struct modu_node *callee_mnode = &the_dyn_call_graph.modu_nodes[callee_m_ix];
+ struct modu_edge *e;
+
+ 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_ix = get_module_idx_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_ix = get_module_idx_from_func_glob_uid (callee->guid);
+ if (callee_m_ix != m_ix)
+ {
+ if (callees->count >= cutoff_count)
+ modu_graph_add_edge (m_ix, callee_m_ix, 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. */
+ the_dyn_call_graph.modu_nodes = modu_nodes
+ = XNEWVEC (struct modu_node, n_modules);
+ memset (modu_nodes, 0, sizeof (struct modu_node) * n_modules);
+ 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];
+ 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 = *(pointer_set_find_or_insert
+ (the_dyn_call_graph.call_graph_nodes[m_ix], fi_ptr->ident));
+ gcc_assert (node);
+ 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_id_value (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;
+
+}
+
+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;
+}
+
+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 modu (value) to the target modu (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_id_value (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];
+
+ 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].group_ggc_mem =
+ get_group_ggc_mem (get_imported_modus (t_mid));
+}
+
+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_id_value (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;
+}
+
+static int
+ps_add_auxiliary (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 m_id = get_module_id_value (modu);
+
+ 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_id_value (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_id_value (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;
+
+ 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)
+ 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), 0);
+ return 1;
+}
+
+static void
+compute_module_group_groups_1_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_1 (gcov_type cutoff_count)
+{
+ build_modu_graph (cutoff_count);
+ compute_module_group_groups_1_impl ();
+}
+
+static void
+gcov_compute_module_groups_0 (gcov_type cutoff_count)
+{
+ unsigned m_ix;
+ struct gcov_info *gi_ptr;
const char *import_scale_str;
unsigned import_scale = __gcov_lipo_propagate_scale;
@@ -1143,6 +1957,11 @@ gcov_compute_module_groups (gcov_type cutoff_count
{
struct dyn_module_info *mi
= &the_dyn_call_graph.sup_modules[m_ix];
+
+ /* initialize flag field. */
+ gi_ptr = the_dyn_call_graph.modules[m_ix];
+ gi_ptr->mod_info->flag = 0;
+
if (mi->imported_modules)
pointer_set_traverse (mi->imported_modules,
gcov_mark_export_modules, 0, 0, 0);
@@ -1224,7 +2043,9 @@ gcov_write_module_info (const struct gcov_info *mo
gcov_write_tag_length (GCOV_TAG_MODULE_INFO, len);
gcov_write_unsigned (module_info->ident);
gcov_write_unsigned (is_primary);
- gcov_write_unsigned (module_info->is_exported);
+ if (flag_alg_mode == 1 && is_primary)
+ SET_MODULE_INCLUDE_ALL_AUX (module_info);
+ gcov_write_unsigned (module_info->flag);
gcov_write_unsigned (module_info->lang);
gcov_write_unsigned (module_info->num_quote_paths);
gcov_write_unsigned (module_info->num_bracket_paths);
@@ -1264,8 +2085,8 @@ gcov_write_module_info (const struct gcov_info *mo
/* Write out MOD_INFO and its imported modules into gcda file. */
-void
-gcov_write_module_infos (struct gcov_info *mod_info)
+static void
+gcov_write_module_infos_0 (struct gcov_info *mod_info)
{
unsigned imp_len = 0;
const struct dyn_imp_mod **imp_mods;
@@ -1280,12 +2101,29 @@ gcov_write_module_info (const struct gcov_info *mo
for (i = 0; i < imp_len; i++)
{
const struct gcov_info *imp_mod = imp_mods[i]->imp_mod;
- gcov_write_module_info (imp_mod, 0);
+ if (imp_mod != mod_info)
+ gcov_write_module_info (imp_mod, 0);
}
free (imp_mods);
}
}
+/*
+static void
+gcov_write_module_infos_1 (struct gcov_info *mod_info)
+{
+}
+*/
+
+void
+gcov_write_module_infos (struct gcov_info *mod_info)
+{
+ if (flag_alg_mode == 0)
+ return gcov_write_module_infos_0 (mod_info);
+ if (flag_alg_mode == 1)
+ return gcov_write_module_infos_0 (mod_info);
+}
+
/* Compute module groups needed for L-IPO compilation. */
void
@@ -1346,7 +2184,7 @@ gcov_dump_cgraph_node_short (struct dyn_cgraph_nod
mod_info = the_dyn_call_graph.modules[mod_id];
fprintf (stderr, "NODE(%llx) module(%s) func(%u)",
- (long long)node->guid,
+ (long long)node->guid,
mod_info->mod_info->source_filename, func_id);
}
@@ -1448,7 +2286,7 @@ 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)
@@ -1487,5 +2325,41 @@ gcov_dump_callgraph (gcov_type 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_idx (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_idx (modu));
+ return 1;
+}
+
+static void
+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
+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
--
This patch is available for review at http://codereview.appspot.com/7393058
More information about the Gcc-patches
mailing list