Issue 7393058: [google gcc-4_7] new module grouping method

xur

Hi, This is the patch that implements a new module grouping. It's based on module ...

11 years, 1 month ago (2013-02-25 19:19:23 UTC) #1

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

Sign in to reply to this message.

miles_gnu.org

xur@google.com (Rong Xu) writes: > - gcov_unsigned_t is_exported; > + gcov_unsigned_t flag; /* bit 0: ...

11 years, 1 month ago (2013-02-25 23:12:30 UTC) #2

davidxl

The coverage.c related patch is not uploaded properly. Will be reviewed seperately. David https://codereview.appspot.com/7393058/diff/1/gcc/gcov-dump.c File ...

11 years, 1 month ago (2013-02-26 00:49:17 UTC) #3

xur

https://codereview.appspot.com/7393058/diff/1/libgcc/dyn-ipa.c File libgcc/dyn-ipa.c (right): https://codereview.appspot.com/7393058/diff/1/libgcc/dyn-ipa.c#newcode77 libgcc/dyn-ipa.c:77: /* Used by new algo. This dyn_pointer_set only On ...

11 years, 1 month ago (2013-02-26 21:50:01 UTC) #4

davidxl

Can you upload the new patch set? David On Tue, Feb 26, 2013 at 1:50 ...

11 years, 1 month ago (2013-02-26 23:26:41 UTC) #5

xur

Just upload the new patch set to https://codereview.appspot.com/7393058/#ps8001 As we discussed offline, I added a ...

11 years, 1 month ago (2013-02-27 00:06:52 UTC) #6

Just upload the new patch set to
https://codereview.appspot.com/7393058/#ps8001

As we discussed offline, I added a non-strict inclusion mode (default off,
and can be turned on by params or env).
Please pay close attentions to part of code that I remove get_module_idx().
This touches the original algorithm.
The naming conventions is: ident (or id) is always module_ident; idx (or
ix) is ident - 1.
I also changed the parameter of get_module_info() from idx to id.

Thanks,

-Rong

On Tue, Feb 26, 2013 at 3:26 PM, Xinliang David Li <davidxl@google.com>wrote:

> Can you upload the new patch set?
>
> David
>
> On Tue, Feb 26, 2013 at 1:50 PM,  <xur@google.com> wrote:
> >
> > https://codereview.appspot.com/7393058/diff/1/libgcc/dyn-ipa.c
> > File libgcc/dyn-ipa.c (right):
> >
> > https://codereview.appspot.com/7393058/diff/1/libgcc/dyn-ipa.c#newcode77
> > libgcc/dyn-ipa.c:77: /* Used by new algo. This dyn_pointer_set only
> > On 2013/02/26 00:49:17, davidxl wrote:
> >>
> >> algo --> algorithm.
> >
> > Done.
> >
> >
> > https://codereview.appspot.com/7393058/diff/1/libgcc/dyn-ipa.c#newcode79
> > libgcc/dyn-ipa.c:79: module ident.  */
> > On 2013/02/26 00:49:17, davidxl wrote:
> >>
> >> module ident or module idx ?
> >
> >
> > it's module ident. ie we should not see 0 as the key.
> >
> >
> > https://codereview.appspot.com/7393058/diff/1/libgcc/dyn-ipa.c#newcode92
> > libgcc/dyn-ipa.c:92: /* used by new_alg  */
> > On 2013/02/26 00:49:17, davidxl wrote:
> >>
> >> new_algo --> new algorithm.
> >
> > Done.
> >
> >
> > https://codereview.appspot.com/7393058/diff/1/libgcc/dyn-ipa.c#newcode98
> > libgcc/dyn-ipa.c:98: struct modu_node {
> > On 2013/02/26 00:49:17, davidxl wrote:
> >>
> >> { to next line.
> >
> > Done.
> >
> >
> >
> https://codereview.appspot.com/7393058/diff/1/libgcc/dyn-ipa.c#newcode102
> > libgcc/dyn-ipa.c:102: unsigned char visited; /* needed? */
> > On 2013/02/26 00:49:17, davidxl wrote:
> >>
> >> Remove the comment 'needed?'
> >
> >
> > removed this field as it's not used.
> >
> >
> >
> https://codereview.appspot.com/7393058/diff/1/libgcc/dyn-ipa.c#newcode113
> > libgcc/dyn-ipa.c:113: unsigned char visited; /* needed? */
> > On 2013/02/26 00:49:17, davidxl wrote:
> >>
> >> Remove the field comment.
> >
> > done.
> >
> >
> >
> https://codereview.appspot.com/7393058/diff/1/libgcc/dyn-ipa.c#newcode189
> > libgcc/dyn-ipa.c:189: static int flag_modu_merge_edges = 1;
> > On 2013/02/26 00:49:17, davidxl wrote:
> >>
> >> These two flags should have corresponding --param=
> >
> > Done.
> >
> >
> >
> https://codereview.appspot.com/7393058/diff/1/libgcc/dyn-ipa.c#newcode194
> > libgcc/dyn-ipa.c:194: #endif
> > On 2013/02/26 00:49:17, davidxl wrote:
> >>
> >> Use __gcov_lipo_max_mem which has the value specified by
> >> --param=max-lipo-mem=...
> >
> >
> > Done.
> >
> >
> https://codereview.appspot.com/7393058/diff/1/libgcc/dyn-ipa.c#newcode253
> > libgcc/dyn-ipa.c:253:
> > The ident is 1 based (started from 1) while idx is 0 based.
> > In the original implementation, ident is used as pointer_set key, and
> > idx is used to access the static arrays. Here I'm using the same way.
> > But it's pretty confusing. I like the idea of using ident exclusively.
> > we will be wasting a little bit memory but the code is cleaner.
> >
> > I'll change this in my up-coming patch.
> >
> >
> > On 2013/02/26 00:49:17, davidxl wrote:
> >>
> >> Why is this interface needed? Can get_module_idx be used instead? Or
> >
> > get rid of
> >>
> >> get_module_idx, and use ident consistently (and fix up limited array
> >
> > reference
> >>
> >> by 1). get_module_idx_from_guid should also be changed to
> >> get_module_ident_from_guid
> >
> >
> >
> https://codereview.appspot.com/7393058/diff/1/libgcc/dyn-ipa.c#newcode339
> > libgcc/dyn-ipa.c:339: gcc_assert (m_ix != 0);
> > On 2013/02/26 00:49:17, davidxl wrote:
> >>
> >> module id may be insane. Should be handled here.
> >
> >
> > I was thinking to add a check here. But we don't found a check in
> > get_module_idx() or inserting the ident in imp_mod_set_insert. So I
> > thought the insane id is not that often.
> >
> > I'll add a check here. I need to think what to do if we see an insane
> > id.
> >
> >
> >
> https://codereview.appspot.com/7393058/diff/1/libgcc/dyn-ipa.c#newcode340
> > libgcc/dyn-ipa.c:340: return
> > the_dyn_call_graph.sup_modules[m_ix-1].exported_to;
> > On 2013/02/26 00:49:17, davidxl wrote:
> >>
> >> The input m_ix should be normalized to zero based idx already. If
> >> get_module_ident is used consistently, the parameter name should be
> >
> > changed to
> >>
> >> module_ident.
> >
> >
> > Done.
> >
> >
> >
> https://codereview.appspot.com/7393058/diff/1/libgcc/dyn-ipa.c#newcode367
> > libgcc/dyn-ipa.c:367: = pointer_set_create (imp_mod_get_key);
> > On 2013/02/26 00:49:17, davidxl wrote:
> >>
> >> split this into two statements
> >
> >
> > Done.
> >
> >
> >
> https://codereview.appspot.com/7393058/diff/1/libgcc/dyn-ipa.c#newcode456
> > libgcc/dyn-ipa.c:456: if (flag_alg_mode == 1)
> > On 2013/02/26 00:49:17, davidxl wrote:
> >>
> >> Define enum for algorithms.
> >
> >
> > Done.
> >
> >
> >
> https://codereview.appspot.com/7393058/diff/1/libgcc/dyn-ipa.c#newcode728
> > libgcc/dyn-ipa.c:728: pointer_set_destroy_2 (struct dyn_pointer_set
> > *pset)
> > On 2013/02/26 00:49:17, davidxl wrote:
> >>
> >> better interface name.
> >
> >
> > Done.
> >
> >
> >
> https://codereview.appspot.com/7393058/diff/1/libgcc/dyn-ipa.c#newcode731
> > libgcc/dyn-ipa.c:731: XDELETEVEC (pset->slots);
> > On 2013/02/26 00:49:17, davidxl wrote:
> >>
> >> Unused i?
> >
> >
> > Done.
> >
> >
> >
> https://codereview.appspot.com/7393058/diff/1/libgcc/dyn-ipa.c#newcode810
> > libgcc/dyn-ipa.c:810: /* Returns nonzero if PSET contains P.  P must be
> > nonnull.
> > Fixed
> >
> > On 2013/02/26 00:49:17, davidxl wrote:
> >>
> >> The comment is not matching.
> >
> >
> >
> https://codereview.appspot.com/7393058/diff/1/libgcc/dyn-ipa.c#newcode828
> > libgcc/dyn-ipa.c:828: n = 0;
> > Not likely. all the slots (upon creation and expansion) are initialized
> > to 0.
> >
> >
> > On 2013/02/26 00:49:17, davidxl wrote:
> >>
> >> Is it possible that there is no empty slot -- thus this cause infinite
> >
> > loop?
> >
> >
> >
> https://codereview.appspot.com/7393058/diff/1/libgcc/dyn-ipa.c#newcode1254
> > libgcc/dyn-ipa.c:1254: static int dyn_fibheap_comp_data (dyn_fibheap_t,
> > dyn_fibheapkey_t, void *, fibnode_t);
> > On 2013/02/26 00:49:17, davidxl wrote:
> >>
> >> wrap long line.
> >
> >
> > Done.
> >
> >
> >
> https://codereview.appspot.com/7393058/diff/1/libgcc/dyn-ipa.c#newcode1281
> > libgcc/dyn-ipa.c:1281: dyn_fibheap_compare (dyn_fibheap_t heap
> > ATTRIBUTE_UNUSED, fibnode_t a, fibnode_t b)
> > On 2013/02/26 00:49:17, davidxl wrote:
> >>
> >> wrap long line.
> >
> >
> > Done.
> >
> >
> >
> https://codereview.appspot.com/7393058/diff/1/libgcc/dyn-ipa.c#newcode1291
> > libgcc/dyn-ipa.c:1291: dyn_fibheap_comp_data (dyn_fibheap_t heap,
> > dyn_fibheapkey_t key, void *data, fibnode_t b)
> > On 2013/02/26 00:49:17, davidxl wrote:
> >>
> >> wrap long line.
> >
> >
> > Done.
> >
> >
> >
> https://codereview.appspot.com/7393058/diff/1/libgcc/dyn-ipa.c#newcode1532
> > libgcc/dyn-ipa.c:1532: /* Compute module grouping using CUTOFF_COUNT as
> > the hot edge
> > On 2013/02/26 00:49:17, davidxl wrote:
> >>
> >> One new line above.
> >
> >
> > Done.
> >
> >
> >
> https://codereview.appspot.com/7393058/diff/1/libgcc/dyn-ipa.c#newcode1542
> > libgcc/dyn-ipa.c:1542: case 0:
> > On 2013/02/26 00:49:17, davidxl wrote:
> >>
> >> Name methods with _1, _0 properly: _1 is
> >
> > 'inclusion_based_with_priority'. The _0
> >>
> >> is the old algorithm: 'eager_propagation'.
> >
> >
> > Done.
> >
> >
> >
> https://codereview.appspot.com/7393058/diff/1/libgcc/dyn-ipa.c#newcode1569
> > libgcc/dyn-ipa.c:1569: e = XNEW (struct modu_edge);
> > On 2013/02/26 00:49:17, davidxl wrote:
> >>
> >> use XCNEW
> >
> >
> > Done.
> >
> >
> >
> https://codereview.appspot.com/7393058/diff/1/libgcc/dyn-ipa.c#newcode1582
> > libgcc/dyn-ipa.c:1582: modu_graph_process_dyn_cgraph_node (struct
> > dyn_cgraph_node *node,
> > On 2013/02/26 00:49:17, davidxl wrote:
> >>
> >> Missing comment.
> >
> >
> > Done.
> >
> >
> >
> https://codereview.appspot.com/7393058/diff/1/libgcc/dyn-ipa.c#newcode1613
> > libgcc/dyn-ipa.c:1613: = XNEWVEC (struct modu_node, n_modules);
> > On 2013/02/26 00:49:17, davidxl wrote:
> >>
> >> Use XCNEWVEC
> >
> >
> > Done.
> >
> >
> >
> https://codereview.appspot.com/7393058/diff/1/libgcc/dyn-ipa.c#newcode1630
> > libgcc/dyn-ipa.c:1630: gcc_assert (node);
> > On 2013/02/26 00:49:17, davidxl wrote:
> >>
> >> Avoid assertion -- add error prints -- similarly for other assertions.
> >
> >
> > Done.
> >
> >
> >
> https://codereview.appspot.com/7393058/diff/1/libgcc/dyn-ipa.c#newcode1660
> > libgcc/dyn-ipa.c:1660: get_group_ggc_mem (struct dyn_pointer_set *s)
> > On 2013/02/26 00:49:17, davidxl wrote:
> >>
> >> Missing comments.
> >
> >
> > Done.
> >
> >
> >
> https://codereview.appspot.com/7393058/diff/1/libgcc/dyn-ipa.c#newcode1668
> > libgcc/dyn-ipa.c:1668: static gcov_unsigned_t
> > On 2013/02/26 00:49:17, davidxl wrote:
> >>
> >> Missing comments
> >
> >
> > Done.
> >
> >
> >
> https://codereview.appspot.com/7393058/diff/1/libgcc/dyn-ipa.c#newcode1727
> > libgcc/dyn-ipa.c:1727: pointer_set_traverse (s_imported_mods,
> > modu_add_auxiliary_1, &t_mid, &count, 0);
> > On 2013/02/26 00:49:17, davidxl wrote:
> >>
> >> wrap long line.
> >
> >
> > Done.
> >
> >
> >
> https://codereview.appspot.com/7393058/diff/1/libgcc/dyn-ipa.c#newcode1727
> > libgcc/dyn-ipa.c:1727: pointer_set_traverse (s_imported_mods,
> > modu_add_auxiliary_1, &t_mid, &count, 0);
> > On 2013/02/26 00:49:17, davidxl wrote:
> >>
> >> wrap long line.
> >
> >
> > Done.
> >
> >
> >
> https://codereview.appspot.com/7393058/diff/1/libgcc/dyn-ipa.c#newcode1735
> > libgcc/dyn-ipa.c:1735: ps_check_ggc_mem (const void *value,
> > On 2013/02/26 00:49:17, davidxl wrote:
> >>
> >> Comment needed.
> >
> >
> > Done.
> >
> >
> >
> https://codereview.appspot.com/7393058/diff/1/libgcc/dyn-ipa.c#newcode1817
> > libgcc/dyn-ipa.c:1817: return 0;
> > Will discuss this off-line.
> >
> >
> > On 2013/02/26 00:49:17, davidxl wrote:
> >>
> >> This constraints might be too strong. For instance, if one of the
> >
> > exported_to
> >>
> >> module (which is not the hottest) has the memory limit exceeded -- it
> >
> > will block
> >>
> >> other exported_to modules from benefiting from the newly added aux
> >
> > module.
> >
> >> Since the the edges are processed in priority order, it should ok to
> >
> > relax this
> >>
> >> to allow propagation even when exported_to module is too large. This
> >
> > still has
> >>
> >> the good nature of the inclusion based algo -- because the most
> >
> > critical part of
> >>
> >> the aux groups are still shared in the hierarchy.
> >
> >
> >
> https://codereview.appspot.com/7393058/diff/1/libgcc/dyn-ipa.c#newcode2116
> > libgcc/dyn-ipa.c:2116: */
> > On 2013/02/26 00:49:17, davidxl wrote:
> >>
> >> Remove this.
> >
> >
> > Done.
> >
> > https://codereview.appspot.com/7393058/
>

Sign in to reply to this message.

davidxl

https://codereview.appspot.com/7393058/diff/8001/libgcc/dyn-ipa.c File libgcc/dyn-ipa.c (right): https://codereview.appspot.com/7393058/diff/8001/libgcc/dyn-ipa.c#newcode235 libgcc/dyn-ipa.c:235: /* Return module_id. FUNC_GUID is the global unique id. ...

11 years, 1 month ago (2013-02-27 00:40:31 UTC) #7

xur

11 years, 1 month ago (2013-02-27 00:57:04 UTC) #8

https://codereview.appspot.com/7393058/diff/8001/libgcc/dyn-ipa.c
File libgcc/dyn-ipa.c (right):

https://codereview.appspot.com/7393058/diff/8001/libgcc/dyn-ipa.c#newcode1212
libgcc/dyn-ipa.c:1212: mod_id = get_module_id_from_func_glob_uid (node->guid) -
1;
Send the wrong patch.
Actually. This should be
mod_id = get_module_id_from_func_glob_uid (node->guid);

On 2013/02/27 00:40:31, davidxl wrote:
> Change var name from mod_id to mod_idx

https://codereview.appspot.com/7393058/diff/8001/libgcc/dyn-ipa.c#newcode1232
libgcc/dyn-ipa.c:1232: callee_mod_id
Same as above. -1 should be removed.

On 2013/02/27 00:40:31, davidxl wrote:
> --> callee_mod_idx

https://codereview.appspot.com/7393058/diff/8001/libgcc/dyn-ipa.c#newcode1250
libgcc/dyn-ipa.c:1250: = get_module_info (callee_mod_id);
This is ok.

On 2013/02/27 00:40:31, davidxl wrote:
> Should be get_module_info (callee_mod_idx + 1).
> 
> You should carefully check to make sure NO interfaces takes idx as parameters,
> and no interface returns idx.

https://codereview.appspot.com/7393058/diff/8001/libgcc/dyn-ipa.c#newcode2276
libgcc/dyn-ipa.c:2276: /* Dumper function for NODE.   M is the module id and F
is the function id.  */
On 2013/02/27 00:40:31, davidxl wrote:
> M is module_ident -1

Done.

Sign in to reply to this message.

Issue 7393058: [google gcc-4_7] new module grouping method

Patch Set 1 #

Patch Set 2 : [google gcc-4_7] new module grouping algorithm patchset2 #

Patch Set 3 : [google gcc-4_7] new module grouping method patchset3 #

Messages