Make ipa-reference bitmaps dense

[Jan Hubicka <hubicka at ucw dot cz>]

Hi,
this patch makes ipa-reference to assign sequential IDS to the static
variables to make bitmaps more dense. DECL_UID is not very good choice
since at WPA time just very small percentage of DECLs are static vars.
The memory use for ipa-reference bitmaps after patch is 83MB compared to
197MB before the patch.

More savings are posible by inveting the bitmaps - the pass collect
static not written/read so there is no need to check what decls are
actually tracked by the pass or not.  Since we need hash map lookup
anyway it is eas yto save statics read/written instead which is smaller
overall.

I will do this incrementally.
Honza

Index: ChangeLog
===================================================================
--- ChangeLog	(revision 276941)
+++ ChangeLog	(working copy)
@@ -1,3 +1,17 @@
+2019-10-13  Jan Hubicka  <hubicka@ucw.cz>
+
+	* ipa-reference.h (ipa_reference_var_uid): Move offline.
+	* ipa-reference.c (reference_vars_map_t): new type.
+	(ipa_reference_vars_map, ipa_reference_vars_uids): New static vars.
+	(ipa_reference_var_uid): Implement.
+	(is_improper): Do not check bitmap for id==-1
+	(get_static_name): Update.
+	(ipa_init): Initialize new datastructures.
+	(analyze_function): Do not recompute ids.
+	(propagate): Free reference_vars_to_consider.
+	(stream_out_bitmap): Update.
+	(ipa_reference_read_optimization_summary): Update.
+
 2019-10-13  Nathan Sidwell  <nathan@acm.org>
 
 	* gengtype-lex.l (CXX_KEYWORD): Add 'mutable'.
Index: ipa-reference.c
===================================================================
--- ipa-reference.c	(revision 276935)
+++ ipa-reference.c	(working copy)
@@ -93,9 +93,10 @@ typedef struct ipa_reference_vars_info_d
 
 /* This map contains all of the static variables that are
    being considered by the compilation level alias analysis.  */
-typedef hash_map<int_hash <unsigned int, -1U>, tree>
-	 reference_vars_to_consider_t;
-static reference_vars_to_consider_t *reference_vars_to_consider;
+typedef hash_map<tree, int> reference_vars_map_t;
+static reference_vars_map_t *ipa_reference_vars_map;
+static int ipa_reference_vars_uids;
+static vec<tree> *reference_vars_to_consider;
 
 /* Set of all interesting module statics.  A bit is set for every module
    static we are considering.  This is added to the local info when asm
@@ -137,6 +138,31 @@ public:
 
 static ipa_ref_opt_summary_t *ipa_ref_opt_sum_summaries = NULL;
 
+/* Return ID used by ipa-reference bitmaps.  -1 if failed.  */
+int
+ipa_reference_var_uid (tree t)
+{
+  if (!ipa_reference_vars_map)
+    return -1;
+  int *id = ipa_reference_vars_map->get
+    (symtab_node::get (t)->ultimate_alias_target (NULL)->decl);
+  if (!id)
+    return -1;
+  return *id;
+}
+
+/* Return ID used by ipa-reference bitmaps.  Create new entry if
+   T is not in map.  Set EXISTED accordinly  */
+int
+ipa_reference_var_get_or_insert_uid (tree t, bool *existed)
+{
+  int &id = ipa_reference_vars_map->get_or_insert
+    (symtab_node::get (t)->ultimate_alias_target (NULL)->decl, existed);
+  if (!*existed)
+    id = ipa_reference_vars_uids++;
+  return id;
+}
+
 /* Return the ipa_reference_vars structure starting from the cgraph NODE.  */
 static inline ipa_reference_vars_info_t
 get_reference_vars_info (struct cgraph_node *node)
@@ -257,7 +283,9 @@ is_improper (symtab_node *n, void *v ATT
 static inline bool
 is_proper_for_analysis (tree t)
 {
-  if (bitmap_bit_p (ignore_module_statics, ipa_reference_var_uid (t)))
+  int id = ipa_reference_var_uid (t);
+
+  if (id != -1 && bitmap_bit_p (ignore_module_statics, id))
     return false;
 
   if (symtab_node::get (t)
@@ -273,7 +301,7 @@ is_proper_for_analysis (tree t)
 static const char *
 get_static_name (int index)
 {
-  return fndecl_name (*reference_vars_to_consider->get (index));
+  return fndecl_name ((*reference_vars_to_consider)[index]);
 }
 
 /* Dump a set of static vars to FILE.  */
@@ -414,8 +442,17 @@ ipa_init (void)
 
   ipa_init_p = true;
 
-  if (dump_file)
-    reference_vars_to_consider = new reference_vars_to_consider_t(251);
+  vec_alloc (reference_vars_to_consider, 10);
+
+
+  if (ipa_ref_opt_sum_summaries != NULL)
+    {
+      delete ipa_ref_opt_sum_summaries;
+      ipa_ref_opt_sum_summaries = NULL;
+      delete ipa_reference_vars_map;
+    }
+  ipa_reference_vars_map = new reference_vars_map_t(257);
+  ipa_reference_vars_uids = 0;
 
   bitmap_obstack_initialize (&local_info_obstack);
   bitmap_obstack_initialize (&optimization_summary_obstack);
@@ -424,12 +461,6 @@ ipa_init (void)
 
   if (ipa_ref_var_info_summaries == NULL)
     ipa_ref_var_info_summaries = new ipa_ref_var_info_summary_t (symtab);
-
-  if (ipa_ref_opt_sum_summaries != NULL)
-    {
-      delete ipa_ref_opt_sum_summaries;
-      ipa_ref_opt_sum_summaries = NULL;
-    }
 }
 
 
@@ -464,6 +495,8 @@ analyze_function (struct cgraph_node *fn
   local = init_function_info (fn);
   for (i = 0; fn->iterate_reference (i, ref); i++)
     {
+      int id;
+      bool existed;
       if (!is_a <varpool_node *> (ref->referred))
 	continue;
       var = ref->referred->decl;
@@ -471,22 +504,22 @@ analyze_function (struct cgraph_node *fn
 	continue;
       /* This is a variable we care about.  Check if we have seen it
 	 before, and if not add it the set of variables we care about.  */
-      if (all_module_statics
-	  && bitmap_set_bit (all_module_statics, ipa_reference_var_uid (var)))
+      id = ipa_reference_var_get_or_insert_uid (var, &existed);
+      if (!existed)
 	{
+	  bitmap_set_bit (all_module_statics, id);
 	  if (dump_file)
-	    reference_vars_to_consider->put (ipa_reference_var_uid (var),
-						var);
+	    reference_vars_to_consider->safe_push (var);
 	}
       switch (ref->use)
 	{
 	case IPA_REF_LOAD:
-          bitmap_set_bit (local->statics_read, ipa_reference_var_uid (var));
+          bitmap_set_bit (local->statics_read, id);
 	  break;
 	case IPA_REF_STORE:
 	  if (ref->cannot_lead_to_return ())
 	    break;
-          bitmap_set_bit (local->statics_written, ipa_reference_var_uid (var));
+          bitmap_set_bit (local->statics_written, id);
 	  break;
 	case IPA_REF_ADDR:
 	  break;
@@ -896,7 +929,7 @@ propagate (void)
     }
 
   if (dump_file)
-    delete reference_vars_to_consider;
+    vec_free (reference_vars_to_consider);
   reference_vars_to_consider = NULL;
   return remove_p ? TODO_remove_functions : 0;
 }
@@ -966,7 +999,7 @@ stream_out_bitmap (struct lto_simple_out
     return;
   EXECUTE_IF_AND_IN_BITMAP (bits, ltrans_statics, 0, index, bi)
     {
-      tree decl = *reference_vars_to_consider->get (index);
+      tree decl = (*reference_vars_to_consider) [index];
       lto_output_var_decl_index (ob->decl_state, ob->main_stream, decl);
     }
 }
@@ -984,22 +1017,23 @@ ipa_reference_write_optimization_summary
   auto_bitmap ltrans_statics;
   int i;
 
-  reference_vars_to_consider = new reference_vars_to_consider_t (251);
+  vec_alloc (reference_vars_to_consider, ipa_reference_vars_uids);
+  reference_vars_to_consider->safe_grow (ipa_reference_vars_uids);
 
   /* See what variables we are interested in.  */
   for (i = 0; i < lto_symtab_encoder_size (encoder); i++)
     {
       symtab_node *snode = lto_symtab_encoder_deref (encoder, i);
       varpool_node *vnode = dyn_cast <varpool_node *> (snode);
+      int id;
+
       if (vnode
-	  && bitmap_bit_p (all_module_statics,
-			    ipa_reference_var_uid (vnode->decl))
+	  && (id = ipa_reference_var_uid (vnode->decl)) != -1
 	  && referenced_from_this_partition_p (vnode, encoder))
 	{
 	  tree decl = vnode->decl;
-	  bitmap_set_bit (ltrans_statics, ipa_reference_var_uid (decl));
-	  reference_vars_to_consider->put
-		 (ipa_reference_var_uid (decl), decl);
+	  bitmap_set_bit (ltrans_statics, id);
+	  (*reference_vars_to_consider)[id] = decl;
 	  ltrans_statics_bitcount ++;
 	}
     }
@@ -1055,8 +1089,10 @@ ipa_reference_read_optimization_summary
   unsigned int j = 0;
   bitmap_obstack_initialize (&optimization_summary_obstack);
 
-  if (ipa_ref_opt_sum_summaries == NULL)
-    ipa_ref_opt_sum_summaries = new ipa_ref_opt_summary_t (symtab);
+  gcc_checking_assert (ipa_ref_opt_sum_summaries == NULL);
+  ipa_ref_opt_sum_summaries = new ipa_ref_opt_summary_t (symtab);
+  ipa_reference_vars_map = new reference_vars_map_t(257);
+  ipa_reference_vars_uids = 0;
 
   all_module_statics = BITMAP_ALLOC (&optimization_summary_obstack);
 
@@ -1083,8 +1119,11 @@ ipa_reference_read_optimization_summary
 	      unsigned int var_index = streamer_read_uhwi (ib);
 	      tree v_decl = lto_file_decl_data_get_var_decl (file_data,
 							     var_index);
+	      bool existed;
 	      bitmap_set_bit (all_module_statics,
-			      ipa_reference_var_uid (v_decl));
+			      ipa_reference_var_get_or_insert_uid
+				 (v_decl, &existed));
+	      gcc_checking_assert (!existed);
 	      if (dump_file)
 		fprintf (dump_file, " %s", fndecl_name (v_decl));
 	    }
@@ -1235,6 +1274,8 @@ ipa_reference_c_finalize (void)
     {
       delete ipa_ref_opt_sum_summaries;
       ipa_ref_opt_sum_summaries = NULL;
+      delete ipa_reference_vars_map;
+      ipa_reference_vars_map = NULL;
     }
 
   if (ipa_init_p)
Index: ipa-reference.h
===================================================================
--- ipa-reference.h	(revision 276935)
+++ ipa-reference.h	(working copy)
@@ -25,12 +25,7 @@ along with GCC; see the file COPYING3.
 bitmap ipa_reference_get_not_read_global (struct cgraph_node *fn);
 bitmap ipa_reference_get_not_written_global (struct cgraph_node *fn);
 void ipa_reference_c_finalize (void);
-
-inline int
-ipa_reference_var_uid (tree t)
-{
-  return DECL_UID (symtab_node::get (t)->ultimate_alias_target (NULL)->decl);
-}
+int ipa_reference_var_uid (tree t);
 
 #endif  /* GCC_IPA_REFERENCE_H  */