Patchwork ping again - Show hash table stats when -fmem-report

login
register
mail settings
Submitter Dimitrios Apostolou
Date July 8, 2012, 5:31 a.m.
Message ID <alpine.LNX.2.02.1207080746120.4288@localhost.localdomain>
Download mbox | patch
Permalink /patch/169621/
State New
Headers show

Comments

Dimitrios Apostolou - July 8, 2012, 5:31 a.m.
Hi,

This patch adds many nice stats about hash tables when gcc is run with 
-fmem-report. Attached patch tested on x86, no regressions.

Also attached is sample output of -fmem-report when compiling reload.c 
with -O2 -g. Especially interesting is the extreme htab usage in 
var-tracking (ofcourse we already knew that... :-) and maybe symtab's 
slightly high collision rate (given it's a very hot hash table). Moreover 
it's notable that since last year, collision rate for mem_attrs_htab has 
been reduced from around 8 to 1, still not good enough but major 
improvement.

Jan: It has negligible overhead in runtime, that's why I'm pushing it 
again as it is. Having compile-time instrumentation is something 
different, but still I'm not quite sure if it's worth the effort. IMHO 
doing separate builds to get memory info is tedious and even I've stopped 
doing them. If it has no overhead maybe it's better as a runtime option?
Any way, compile-time instrumentation can come later.

Finally I repost some of my notes I'd like to get feedback on:

* Is it OK that I included <assert.h> in libiberty's hashtab.c? What's the 
proper way to assert stuff, since gcc_assert() is not accessible?

* Many hash tables are created with htab_create_ggc(), for example 
referenced_vars and default_defs in tree-ssa.c. I collect statistics in 
delete_tree_ssa() but maybe some are not deallocated in there but 
automatically garbage collected?

* Obviously hash table sizes are inflated where two entries might 
reference the same element (for example in symtab_hash) but I don't handle 
this.

* Changes that reduce load factor have been backed out since they brought 
controversy. I still think they are good, at least for symtab. I'll 
measure numbers separately for this after this patch makes it.


Thanks,
Dimitris
dwarf2out.c: file_table hash table statistics:
	slots		251
	used		98 (39.04%)
		valid		98
		deleted		0
	total size	1852  B
		struct htab	64	 B
		table		1004	 B
		one element	8	 B
		all elements	784	 B
	expansions	2
	searches	8788
	collisions	4239
	coll/search	0.4824
Number of expanded macros:                     23596
Average number of tokens per macro expansion:     10

Line Table allocations during the compilation process
Number of ordinary maps used:          498 
Ordinary map used size:                 11k
Number of ordinary maps allocated:    1365 
Ordinary maps allocated size:           31k
Number of macro maps used:              20k
Macro maps used size:                  499k
Macro maps locations size:            2059k
Macro maps size:                      2558k
Duplicated maps locations size:        767k
Total allocated maps size:            2603k
Total used maps size:                 2570k

Memory still allocated at the end of the compilation process
Size   Allocated        Used    Overhead
8            556k        555k         13k
16          1368k       1365k         21k
32          1736k       1727k         20k
64           212k        209k       2120 
128         1400k       1398k         12k
256         1520k       1515k         11k
512         1128k       1123k       9024 
1024         444k        394k       3552 
2048         320k        298k       2560 
4096         252k         76k       2016 
8192         272k        240k       1088 
16384        848k        352k       1696 
32768        288k        288k        288 
65536        128k         64k         64 
131072        128k          0          32 
262144        256k          0          32 
524288        512k        512k         32 
12          5104k       5097k         89k
20           404k        400k       5656 
24          4820k       4797k         61k
28          3140k       3130k         36k
36          1208k       1196k         12k
40           344k        341k       3784 
44          1200k       1196k         11k
48          2648k       2636k         25k
52           384k        378k       3840 
56          1544k       1522k         15k
60            92k         88k        920 
108          348k        338k       3132 
84          2640k       2597k         23k
96          2844k       2796k         24k
92           432k        342k       3888 
68           804k        798k       7236 
176          624k        606k       4992 
100           20k         13k        180 
Total         39M         37M        435k

libcpp symtab string pool:
	identifiers	32361 (100.00%)
	entries		32361 (49.38%)
	deleted		0
	slots		65536
	string bytes	507k (4064  obstack_memory_used)
	table size	256k
	expansions	2
	searches	228153
	collisions	145056
	coll/search	0.6358
	ins/search	0.1418
	avg. entry	16.05 bytes (+/- 7.31)
	longest entry	62
No gimple statistics

??? tree nodes created

(No per-node statistics)
DECL_DEBUG_EXPR  hash: size 1021, 64 elements, 0.005510 collisions
DECL_VALUE_EXPR  hash: size 1021, 1 elements, 0.000000 collisions

tree.c:type_hash_table stats
	slots		8191
	used		5142 (62.78%)
		valid		5142
		deleted		0
	total size	72 kB
		struct htab	64	 B
		table		31	kB
		one element	8	 B
		all elements	40	kB
	expansions	3
	searches	20481
	collisions	24507
	coll/search	1.1966

tree-ssa.c stats
	81 referenced_vars hash tables:
		total expansions	97
		total searches		62834
		total collisions	29961
		total coll/search	0.4768
	81 default_defs hash tables
		total expansions	0
		total searches		14545
		total collisions	3818
		total coll/search	0.2625

emit-rtl.c:mem_attrs_htab hash table:
	slots		8191
	used		3833 (46.80%)
		valid		3833
		deleted		0
	total size	151 kB
		struct htab	64	 B
		table		31	kB
		one element	32	 B
		all elements	119	kB
	expansions	7
	searches	20961
	collisions	20451
	coll/search	0.9757

cgraph.c hash table stats:
	3 cgraph_node->call_site_hash hash tables:
		total expansions	3
		total searches		1418
		total collisions	741
		total coll/search	0.5226

var-tracking.c stats
	10634 vars->htab hash tables:
		total expansions	4008
		total searches		1683802
		total collisions	790437
		total coll/search	0.4694
	45 changed_variables hash tables
		total expansions	2406
		total searches		133525
		total collisions	72294
		total coll/search	0.5414
	45 dropped_values hash tables
		total expansions	0
		total searches		58782
		total collisions	4
		total coll/search	0.0001

cselib stats for 1755 hash tables
	total expansions	214
	total searches		173364
	total collisions	55665
	total coll/search	0.3211

symtab.c:symtab_hash hash table stats:
	slots		2039
	used		1142 (56.01%)
		valid		189
		deleted		953
	total size	40 kB
		struct htab	64	 B
		table		8156	 B
		one element	176	 B
		all elements	32	kB
	expansions	7
	searches	330240
	collisions	162513
	coll/search	0.4921

symtab.c:assembler_name_hash hash table stats:
	Empty!


Alias oracle query stats:
  refs_may_alias_p: 838 disambiguations, 1068 queries
  ref_maybe_used_by_call_p: 15382 disambiguations, 1105 queries
  call_may_clobber_ref_p: 15351 disambiguations, 15351 queries

PTA query stats:
  pt_solution_includes: 3545 disambiguations, 36431 queries
  pt_solutions_intersect: 241 disambiguations, 11391 queries

2012-07-07 Dimitrios Apostolou <jimis@gmx.net>

	Print various statistics about hash tables when called with
	-fmem-report. If the tables are created once use
	htab_dump_statistics(), if they are created/destroyed multiple
	times then introduce global variables to track statistics.

	* gcc/Makefile.in: (toplev.o) toplev.o depends on cselib.h.
	* cgraph.c, cgraph.h:
	(cgraph_dump_stats): New function to dump stats about hash tables.
	* gcc/symtab.c, cgraph.h:
	(symtab_dump_stats): New function to dump stats about hash tables.
	* cgraph.c: (call_site_hash_{num,expands,searches,collisions}):
	New globals to keep statistics about call_site_hash hash tables.
	(cgraph_remove_node_callees,cgraph_remove_node): if (mem_report)
	then keep statistics about hash tables.
	* cselib.c, cselib.h (cselib_dump_stats): New function to dump
	stats about cselib_hash_table.
	* cselib.c (cselib_htab_{num,expands,searches,collisions}): New
	globals to keep hash table statistics.
	(cselib_finish): if (mem_report) keep hash table statistics.
	* dwarf2out.c (dwarf2out_finish): Call htab_dump_statistics() if
	-fmem_report.
	* emit-rtl.c, emit-rtl.h (mem_attrs_dump_stats): New function to
	dump statistics about mem_attrs_htab hash table.
	* tree.h, tree-ssa.c (tree_ssa_dump_stats): New function to print
	statistics about all referenced_vars and default_defs hash tables.
	* tree-ssa.c (default_defs_{num,expands,searches,collisions})
	(referenced_vars_{num,expands,searches,collisions}): new globals
	to keep statistics about hash tables.
	(delete_tree_ssa): Keep statistics for hash tables by
	increasing the new global variables.
	* tree.c (dump_tree_statistics): Call tree_ssa_dump_stats().
	(print_type_hash_statistics): Used the new htab_dump_statistics()
	function.
	* var-tracking.c (vars_htab_{num,expands,searches,collisions})
	(dropval_htab_{num,expands,searches,collisions})
	(cv_htab_{num,expands,searches,collisions}): new globals to keep
	hash table statistics.
	(shared_hash_destroy, vt_finalize): Keep statistics by
	increasing values of new global variables if -fmem-report.
	* var-tracking.c, rtl.h (vt_dump_stats): New function to dump
	stats about vars->htab, dropped_variables and value_chains hash
	tables.
	* toplev.c: Included cselib.h for cselib_dump_stats().
	(dump_memory_report): Call all the above functions to provide
	better statistics.

	* hashtab.c, hashtab.h: Added "expands" variable to htab_t for
	tracking total times the hash table was expanded.
	* hashtab.c, hashtab.h (htab_dump_statistics, htab_collisions_num)
	(htab_searches_num, htab_expands_num): New functions for  statistics.
	* hashtab.c: Included assert.h for checks in htab_dump_statistics.
	* cgraph.h, varpool.c (varpool_dump_stats): New function to dump
	stats about varpool_hash hash table.

	* libcpp/symtab.c, symtab.h: Added "expands" variable to
	hash_table type for tracking total times the hash table was
	expanded.
	* symtab.c (ht_dump_statistics): Beautified stats output.

Patch

=== modified file 'gcc/Makefile.in'
--- gcc/Makefile.in	2012-07-04 09:15:09 +0000

+++ gcc/Makefile.in	2012-07-07 19:28:14 +0000

@@ -2678,7 +2678,7 @@  toplev.o : toplev.c $(CONFIG_H) $(SYSTEM

    langhooks.h insn-flags.h $(CFGLOOP_H) hosthooks.h \
    $(CGRAPH_H) $(COVERAGE_H) alloc-pool.h $(GGC_H) \
    $(OPTS_H) params.def tree-mudflap.h $(TREE_PASS_H) $(GIMPLE_H) \
-   tree-ssa-alias.h $(PLUGIN_H) realmpfr.h tree-diagnostic.h \

+   tree-ssa-alias.h $(PLUGIN_H) cselib.h realmpfr.h tree-diagnostic.h \

    $(TREE_PRETTY_PRINT_H) opts-diagnostic.h $(COMMON_TARGET_H)
 
 hwint.o : hwint.c $(CONFIG_H) $(SYSTEM_H) $(DIAGNOSTIC_CORE_H)

=== modified file 'gcc/cgraph.c'
--- gcc/cgraph.c	2012-05-31 20:19:00 +0000

+++ gcc/cgraph.c	2012-07-07 19:23:32 +0000

@@ -1062,6 +1062,13 @@  cgraph_update_edges_for_call_stmt (gimpl

 }
 
 
+/* Keep statistics about call_site_hash hash tables. */

+static unsigned int call_site_hash_num;

+static unsigned long call_site_hash_expands;

+static unsigned long call_site_hash_searches;

+static unsigned long call_site_hash_collisions;

+

+

 /* Remove all callees from the node.  */
 
 void
@@ -1092,6 +1099,16 @@  cgraph_node_remove_callees (struct cgrap

   node->callees = NULL;
   if (node->call_site_hash)
     {
+      if (mem_report)

+	{

+	  call_site_hash_num++;

+	  call_site_hash_expands +=

+	    htab_expands_num (node->call_site_hash);

+	  call_site_hash_searches +=

+	    htab_searches_num (node->call_site_hash);

+	  call_site_hash_collisions +=

+	    htab_collisions_num (node->call_site_hash);

+	}

       htab_delete (node->call_site_hash);
       node->call_site_hash = NULL;
     }
@@ -1248,6 +1265,16 @@  cgraph_remove_node (struct cgraph_node *

   node->symbol.decl = NULL;
   if (node->call_site_hash)
     {
+      if (mem_report)

+	{

+	  call_site_hash_num++;

+	  call_site_hash_expands +=

+	    htab_expands_num (node->call_site_hash);

+	  call_site_hash_searches +=

+	    htab_searches_num (node->call_site_hash);

+	  call_site_hash_collisions +=

+	    htab_collisions_num (node->call_site_hash);

+	}

       htab_delete (node->call_site_hash);
       node->call_site_hash = NULL;
     }
@@ -2453,4 +2480,18 @@  verify_cgraph (void)

   FOR_EACH_FUNCTION (node)
     verify_cgraph_node (node);
 }
+

+void

+cgraph_dump_stats (void)

+{

+  fprintf (stderr, "\ncgraph.c hash table stats:\n");

+  fprintf (stderr, "\t%u cgraph_node->call_site_hash hash tables:\n",

+	   call_site_hash_num);

+  fprintf (stderr, "\t\ttotal expansions\t%lu\n", call_site_hash_expands);

+  fprintf (stderr, "\t\ttotal searches\t\t%lu\n", call_site_hash_searches);

+  fprintf (stderr, "\t\ttotal collisions\t%lu\n", call_site_hash_collisions);

+  fprintf (stderr, "\t\ttotal coll/search\t%.4f\n",

+	   (float) call_site_hash_collisions / call_site_hash_searches);

+}

+

 #include "gt-cgraph.h"

=== modified file 'gcc/cgraph.h'
--- gcc/cgraph.h	2012-06-26 10:15:18 +0000

+++ gcc/cgraph.h	2012-07-07 19:23:32 +0000

@@ -492,6 +492,7 @@  void verify_symtab_node (symtab_node);

 bool verify_symtab_base (symtab_node);
 bool symtab_used_from_object_file_p (symtab_node);
 void symtab_make_decl_local (tree);
+void symtab_dump_stats (void);

 
 /* In cgraph.c  */
 void dump_cgraph (FILE *);
@@ -586,6 +587,7 @@  struct cgraph_2node_hook_list *cgraph_ad

 void cgraph_remove_node_duplication_hook (struct cgraph_2node_hook_list *);
 gimple cgraph_redirect_edge_call_stmt_to_callee (struct cgraph_edge *);
 bool cgraph_propagate_frequency (struct cgraph_node *node);
+void cgraph_dump_stats (void);

 
 /* In cgraphunit.c  */
 struct asm_node *add_asm_node (tree);

=== modified file 'gcc/cselib.c'
--- gcc/cselib.c	2012-06-22 01:29:28 +0000

+++ gcc/cselib.c	2012-07-07 19:23:32 +0000

@@ -2691,6 +2691,11 @@  cselib_init (int record_what)

   next_uid = 1;
 }
 
+static unsigned int cselib_htab_num;

+static unsigned long cselib_htab_expands;

+static unsigned long cselib_htab_searches;

+static unsigned long cselib_htab_collisions;

+

 /* Called when the current user is done with cselib.  */
 
 void
@@ -2705,6 +2710,13 @@  cselib_finish (void)

   free_alloc_pool (elt_loc_list_pool);
   free_alloc_pool (cselib_val_pool);
   free_alloc_pool (value_pool);
+  if (mem_report)

+    {

+      cselib_htab_num++;

+      cselib_htab_expands += htab_expands_num (cselib_hash_table);

+      cselib_htab_searches += htab_searches_num (cselib_hash_table);

+      cselib_htab_collisions += htab_collisions_num (cselib_hash_table);

+    }

   cselib_clear_table ();
   htab_delete (cselib_hash_table);
   free (used_regs);
@@ -2807,4 +2819,18 @@  dump_cselib_table (FILE *out)

   fprintf (out, "next uid %i\n", next_uid);
 }
 
+void

+cselib_dump_stats (void)

+{

+  if (cselib_htab_num > 0)

+    {

+      fprintf (stderr, "\ncselib stats for %u hash tables\n", cselib_htab_num);

+      fprintf (stderr, "\ttotal expansions\t%lu\n", cselib_htab_expands);

+      fprintf (stderr, "\ttotal searches\t\t%lu\n", cselib_htab_searches);

+      fprintf (stderr, "\ttotal collisions\t%lu\n", cselib_htab_collisions);

+      fprintf (stderr, "\ttotal coll/search\t%.4f\n",

+	       (float) cselib_htab_collisions / cselib_htab_searches);

+    }

+}

+

 #include "gt-cselib.h"

=== modified file 'gcc/cselib.h'
--- gcc/cselib.h	2012-03-01 16:58:11 +0000

+++ gcc/cselib.h	2012-07-07 19:10:57 +0000

@@ -101,6 +101,7 @@  extern void cselib_add_permanent_equiv (

 extern bool cselib_have_permanent_equivalences (void);
 
 extern void dump_cselib_table (FILE *);
+extern void cselib_dump_stats (void);

 
 /* Return the canonical value for VAL, following the equivalence chain
    towards the earliest (== lowest uid) equivalent value.  */

=== modified file 'gcc/dwarf2out.c'
--- gcc/dwarf2out.c	2012-07-06 07:44:52 +0000

+++ gcc/dwarf2out.c	2012-07-07 19:23:32 +0000

@@ -22206,6 +22206,13 @@  dwarf2out_finish (const char *filename)

 	add_comp_dir_attribute (comp_unit_die ());
     }
 
+  if (mem_report)

+    {

+      fprintf(stderr, "\ndwarf2out.c: file_table hash table statistics:\n");

+      htab_dump_statistics(file_table, sizeof (struct dwarf_file_data));

+    }

+

+

   for (i = 0; i < VEC_length (deferred_locations, deferred_locations_list); i++)
     {
       add_location_or_const_value_attribute (

=== modified file 'gcc/emit-rtl.c'
--- gcc/emit-rtl.c	2012-06-20 01:05:25 +0000

+++ gcc/emit-rtl.c	2012-07-07 19:23:32 +0000

@@ -5504,6 +5504,13 @@  gen_rtx_CONST_VECTOR (enum machine_mode

   return gen_rtx_raw_CONST_VECTOR (mode, v);
 }
 
+void

+mem_attrs_dump_stats (void)

+{

+  fprintf (stderr, "\nemit-rtl.c:mem_attrs_htab hash table:\n");

+  htab_dump_statistics (mem_attrs_htab, sizeof (mem_attrs));

+}

+

 /* Initialise global register information required by all functions.  */
 
 void

=== modified file 'gcc/emit-rtl.h'
--- gcc/emit-rtl.h	2012-06-20 01:05:25 +0000

+++ gcc/emit-rtl.h	2012-07-07 19:23:32 +0000

@@ -68,6 +68,7 @@  extern void set_reg_attrs_for_parm (rtx,

 extern void set_reg_attrs_for_decl_rtl (tree t, rtx x);
 extern void adjust_reg_mode (rtx, enum machine_mode);
 extern int mem_expr_equal_p (const_tree, const_tree);
+extern void mem_attrs_dump_stats (void);

 
 extern bool need_atomic_barrier_p (enum memmodel, bool);
 

=== modified file 'gcc/rtl.h'
--- gcc/rtl.h	2012-06-17 21:12:24 +0000

+++ gcc/rtl.h	2012-07-07 19:23:32 +0000

@@ -2614,6 +2614,7 @@  extern bool expensive_function_p (int);

 
 /* In var-tracking.c */
 extern unsigned int variable_tracking_main (void);
+extern void vt_dump_stats (void);

 
 /* In stor-layout.c.  */
 extern void get_mode_bounds (enum machine_mode, int, enum machine_mode,

=== modified file 'gcc/symtab.c'
--- gcc/symtab.c	2012-05-23 09:23:40 +0000

+++ gcc/symtab.c	2012-07-07 19:23:32 +0000

@@ -750,4 +750,20 @@  symtab_make_decl_local (tree decl)

 
   SYMBOL_REF_WEAK (symbol) = DECL_WEAK (decl);
 }
+

+void symtab_dump_stats (void)

+{

+  fprintf (stderr, "\nsymtab.c:symtab_hash hash table stats:\n");

+  if (symtab_hash != NULL)

+    htab_dump_statistics (symtab_hash, sizeof (union symtab_node_def));

+  else

+    fprintf (stderr, "\tEmpty!\n\n");

+  

+  fprintf (stderr, "\nsymtab.c:assembler_name_hash hash table stats:\n");

+  if (assembler_name_hash != NULL)

+    htab_dump_statistics (assembler_name_hash, sizeof (union symtab_node_def));

+  else

+    fprintf (stderr, "\tEmpty!\n\n");

+}

+

 #include "gt-symtab.h"

=== modified file 'gcc/toplev.c'
--- gcc/toplev.c	2012-06-19 19:55:33 +0000

+++ gcc/toplev.c	2012-07-07 19:23:32 +0000

@@ -75,6 +75,7 @@  along with GCC; see the file COPYING3.

 #include "gimple.h"
 #include "tree-ssa-alias.h"
 #include "plugin.h"
+#include "cselib.h" 		/* only for cselib_dump_stats() */

 
 #if defined (DWARF2_UNWIND_INFO) || defined (DWARF2_DEBUGGING_INFO)
 #include "dwarf2out.h"
@@ -1768,8 +1769,14 @@  dump_memory_report (bool final)

   dump_line_table_statistics ();
   ggc_print_statistics ();
   stringpool_statistics ();
-  dump_tree_statistics ();

   dump_gimple_statistics ();
+  dump_tree_statistics ();

+  mem_attrs_dump_stats ();

+  cgraph_dump_stats ();

+  if (flag_var_tracking)

+    vt_dump_stats ();

+  cselib_dump_stats ();

+  symtab_dump_stats();

   dump_rtx_statistics ();
   dump_alloc_pool_statistics ();
   dump_bitmap_statistics ();

=== modified file 'gcc/tree-ssa.c'
--- gcc/tree-ssa.c	2012-05-31 20:19:00 +0000

+++ gcc/tree-ssa.c	2012-07-07 19:23:32 +0000

@@ -1103,6 +1103,12 @@  uid_ssaname_map_hash (const void *item)

   return ((const_tree)item)->ssa_name.var->decl_minimal.uid;
 }
 
+/* hash table statistics */

+

+static unsigned long referenced_vars_expands, default_defs_expands;

+static unsigned long referenced_vars_searches, default_defs_searches;

+static unsigned long referenced_vars_collisions, default_defs_collisions;

+static unsigned int referenced_vars_num, default_defs_num;

 
 /* Initialize global DFA and SSA structures.  */
 
@@ -1167,6 +1173,25 @@  delete_tree_ssa (void)

 	  *DECL_VAR_ANN_PTR (var) = NULL;
 	}
     }
+

+  if (mem_report)

+    {

+      referenced_vars_num++;

+      referenced_vars_expands +=

+	htab_expands_num (gimple_referenced_vars (cfun));

+      referenced_vars_searches +=

+	htab_searches_num (gimple_referenced_vars (cfun));

+      referenced_vars_collisions +=

+	htab_collisions_num (gimple_referenced_vars (cfun));

+      default_defs_num++;

+      default_defs_expands +=

+	htab_expands_num (cfun->gimple_df->default_defs);

+      default_defs_searches +=

+	htab_searches_num (cfun->gimple_df->default_defs);

+      default_defs_collisions +=

+	htab_collisions_num (cfun->gimple_df->default_defs);

+    }

+

   htab_delete (gimple_referenced_vars (cfun));
   cfun->gimple_df->referenced_vars = NULL;
 
@@ -1189,6 +1214,26 @@  delete_tree_ssa (void)

   redirect_edge_var_map_destroy ();
 }
 
+void

+tree_ssa_dump_stats (void)

+{

+  fprintf (stderr, "\ntree-ssa.c stats\n");

+  

+  fprintf (stderr, "\t%u referenced_vars hash tables:\n", referenced_vars_num);

+  fprintf (stderr, "\t\ttotal expansions\t%lu\n", referenced_vars_expands);

+  fprintf (stderr, "\t\ttotal searches\t\t%lu\n", referenced_vars_searches);

+  fprintf (stderr, "\t\ttotal collisions\t%lu\n", referenced_vars_collisions);

+  fprintf (stderr, "\t\ttotal coll/search\t%.4f\n",

+	   (float) referenced_vars_collisions / referenced_vars_searches);

+

+  fprintf (stderr, "\t%u default_defs hash tables\n", default_defs_num);

+  fprintf (stderr, "\t\ttotal expansions\t%lu\n", default_defs_expands);

+  fprintf (stderr, "\t\ttotal searches\t\t%lu\n", default_defs_searches);

+  fprintf (stderr, "\t\ttotal collisions\t%lu\n", default_defs_collisions);

+  fprintf (stderr, "\t\ttotal coll/search\t%.4f\n",

+	   (float) default_defs_collisions / default_defs_searches);

+}

+

 /* Return true if the conversion from INNER_TYPE to OUTER_TYPE is a
    useless type conversion, otherwise return false.
 

=== modified file 'gcc/tree.c'
--- gcc/tree.c	2012-07-04 10:36:07 +0000

+++ gcc/tree.c	2012-07-07 19:23:32 +0000

@@ -6365,10 +6365,8 @@  type_hash_marked_p (const void *p)

 static void
 print_type_hash_statistics (void)
 {
-  fprintf (stderr, "Type hash: size %ld, %ld elements, %f collisions\n",

-	   (long) htab_size (type_hash_table),

-	   (long) htab_elements (type_hash_table),

-	   htab_collisions (type_hash_table));

+  fprintf (stderr, "\ntree.c:type_hash_table stats\n");

+  htab_dump_statistics (type_hash_table, sizeof (struct type_hash));

 }
 
 /* Compute a hash code for a list of attributes (chain of TREE_LIST nodes
@@ -8736,10 +8734,11 @@  dump_tree_statistics (void)

 #else
   fprintf (stderr, "(No per-node statistics)\n");
 #endif
-  print_type_hash_statistics ();

   print_debug_expr_statistics ();
   print_value_expr_statistics ();
   lang_hooks.print_statistics ();
+  print_type_hash_statistics ();

+  tree_ssa_dump_stats ();

 }
 
 #define FILE_FUNCTION_FORMAT "_GLOBAL__%s_%s"

=== modified file 'gcc/tree.h'
--- gcc/tree.h	2012-07-02 18:50:51 +0000

+++ gcc/tree.h	2012-07-07 19:23:32 +0000

@@ -5871,6 +5871,7 @@  struct GTY(()) tree_vec_map {

 /* In tree-ssa.c */
 
 tree target_for_debug_bind (tree);
+void tree_ssa_dump_stats (void);

 
 /* In tree-ssa-address.c.  */
 extern tree tree_mem_ref_addr (tree, tree);

=== modified file 'gcc/var-tracking.c'
--- gcc/var-tracking.c	2012-07-06 11:37:36 +0000

+++ gcc/var-tracking.c	2012-07-07 19:23:32 +0000

@@ -1582,6 +1582,11 @@  shared_hash_copy (shared_hash vars)

   return vars;
 }
 
+static unsigned long vars_htab_expands;

+static unsigned long vars_htab_searches;

+static unsigned long vars_htab_collisions;

+static unsigned int vars_htab_num;

+

 /* Decrement reference counter and destroy hash table if not shared
    anymore.  */
 
@@ -1591,6 +1596,13 @@  shared_hash_destroy (shared_hash vars)

   gcc_checking_assert (vars->refcount > 0);
   if (--vars->refcount == 0)
     {
+      if (mem_report)

+	{

+	  vars_htab_num++;

+	  vars_htab_expands += htab_expands_num (vars->htab);

+	  vars_htab_searches += htab_searches_num (vars->htab);

+	  vars_htab_collisions += htab_collisions_num (vars->htab);

+	}

       htab_delete (vars->htab);
       pool_free (shared_hash_pool, vars);
     }
@@ -9209,6 +9221,14 @@  emit_notes_in_bb (basic_block bb, datafl

     }
 }
 
+

+/* Keep stats for dropped_values hash table */

+static unsigned long dropval_htab_expands;

+static unsigned long dropval_htab_searches;

+static unsigned long dropval_htab_collisions;

+static unsigned int dropval_htab_num;

+

+

 /* Emit notes for the whole function.  */
 
 static void
@@ -9260,7 +9280,16 @@  vt_emit_notes (void)

   dataflow_set_destroy (&cur);
 
   if (MAY_HAVE_DEBUG_INSNS)
-    htab_delete (dropped_values);

+    {

+      if (mem_report)

+	{

+	  dropval_htab_num++;

+	  dropval_htab_expands += htab_expands_num (dropped_values);

+	  dropval_htab_searches += htab_searches_num (dropped_values);

+	  dropval_htab_collisions += htab_collisions_num (dropped_values);

+	}

+      htab_delete (dropped_values);

+    }

 
   emit_notes = false;
 }
@@ -9935,6 +9964,12 @@  vt_debug_insns_local (bool skipped ATTRI

   delete_debug_insns ();
 }
 
+/* Keep stats for changed_variables hash table */

+static unsigned long cv_htab_expands;

+static unsigned long cv_htab_searches;

+static unsigned long cv_htab_collisions;

+static unsigned int cv_htab_num;

+

 /* Free the data structures needed for variable tracking.  */
 
 static void
@@ -9959,6 +9994,13 @@  vt_finalize (void)

     }
   free_aux_for_blocks ();
   htab_delete (empty_shared_hash->htab);
+  if (mem_report)

+    {

+      cv_htab_num++;

+      cv_htab_expands += htab_expands_num (changed_variables);

+      cv_htab_searches += htab_searches_num (changed_variables);

+      cv_htab_collisions += htab_collisions_num (changed_variables);

+    }

   htab_delete (changed_variables);
   free_alloc_pool (attrs_pool);
   free_alloc_pool (var_pool);
@@ -9987,6 +10029,36 @@  vt_finalize (void)

   vui_allocated = 0;
 }
 
+void

+vt_dump_stats (void)

+{

+  fprintf (stderr, "\nvar-tracking.c stats\n");

+  

+  fprintf (stderr, "\t%u vars->htab hash tables:\n", vars_htab_num);

+  fprintf (stderr, "\t\ttotal expansions\t%lu\n", vars_htab_expands);

+  fprintf (stderr, "\t\ttotal searches\t\t%lu\n", vars_htab_searches);

+  fprintf (stderr, "\t\ttotal collisions\t%lu\n", vars_htab_collisions);

+  fprintf (stderr, "\t\ttotal coll/search\t%.4f\n",

+	   (float) vars_htab_collisions / vars_htab_searches);

+

+  fprintf (stderr, "\t%u changed_variables hash tables\n", cv_htab_num);

+  fprintf (stderr, "\t\ttotal expansions\t%lu\n", cv_htab_expands);

+  fprintf (stderr, "\t\ttotal searches\t\t%lu\n", cv_htab_searches);

+  fprintf (stderr, "\t\ttotal collisions\t%lu\n", cv_htab_collisions);

+  fprintf (stderr, "\t\ttotal coll/search\t%.4f\n",

+	   (float) cv_htab_collisions / cv_htab_searches);

+

+  if (MAY_HAVE_DEBUG_INSNS)

+    {

+      fprintf (stderr, "\t%u dropped_values hash tables\n", dropval_htab_num);

+      fprintf (stderr, "\t\ttotal expansions\t%lu\n", dropval_htab_expands);

+      fprintf (stderr, "\t\ttotal searches\t\t%lu\n", dropval_htab_searches);

+      fprintf (stderr, "\t\ttotal collisions\t%lu\n", dropval_htab_collisions);

+      fprintf (stderr, "\t\ttotal coll/search\t%.4f\n",

+      	       (float) dropval_htab_collisions / dropval_htab_searches);

+    }

+}

+

 /* The entry point to variable tracking pass.  */
 
 static inline unsigned int

=== modified file 'include/hashtab.h'
--- include/hashtab.h	2010-06-08 06:25:24 +0000

+++ include/hashtab.h	2012-07-07 19:10:57 +0000

@@ -127,6 +127,9 @@  struct GTY(()) htab {

      of collisions fixed for time of work with the hash table. */
   unsigned int collisions;
 
+  /* Number of times we reallocated the table to change its capacity. */

+  unsigned int expands;

+

   /* Pointers to allocate/free functions.  */
   htab_alloc alloc_f;
   htab_free free_f;
@@ -187,6 +190,10 @@  extern void	htab_traverse_noresize (htab

 extern size_t	htab_size (htab_t);
 extern size_t	htab_elements (htab_t);
 extern double	htab_collisions	(htab_t);
+extern void     htab_dump_statistics (htab_t, size_t);

+extern unsigned int    htab_collisions_num (htab_t);

+extern unsigned int    htab_searches_num (htab_t);

+extern unsigned int    htab_expands_num (htab_t);

 
 /* A hash function for pointers.  */
 extern htab_hash htab_hash_pointer;

=== modified file 'libcpp/include/symtab.h'
--- libcpp/include/symtab.h	2011-01-03 20:52:22 +0000

+++ libcpp/include/symtab.h	2012-07-07 19:10:57 +0000

@@ -63,6 +63,7 @@  struct ht

   struct cpp_reader *pfile;
 
   /* Table usage statistics.  */
+  unsigned int expands;

   unsigned int searches;
   unsigned int collisions;
 

=== modified file 'libcpp/symtab.c'
--- libcpp/symtab.c	2009-07-18 02:22:16 +0000

+++ libcpp/symtab.c	2012-07-07 19:10:57 +0000

@@ -219,6 +219,7 @@  ht_expand (hash_table *table)

   table->entries_owned = true;
   table->entries = nentries;
   table->nslots = size;
+  table->expands++;

 }
 
 /* For all nodes in TABLE, callback CB with parameters TABLE->PFILE,
@@ -276,7 +277,7 @@  ht_load (hash_table *ht, hashnode *entri

 void
 ht_dump_statistics (hash_table *table)
 {
-  size_t nelts, nids, overhead, headers;

+  size_t nelts, nids, obmem, headers;

   size_t total_bytes, longest, deleted = 0;
   double sum_of_squares, exp_len, exp_len2, exp2_len;
   hashnode *p, *limit;
@@ -307,34 +308,41 @@  ht_dump_statistics (hash_table *table)

   while (++p < limit);
 
   nelts = table->nelements;
-  overhead = obstack_memory_used (&table->stack) - total_bytes;

+  obmem = obstack_memory_used (&table->stack);

   headers = table->nslots * sizeof (hashnode);
 
-  fprintf (stderr, "\nString pool\nentries\t\t%lu\n",

-	   (unsigned long) nelts);

-  fprintf (stderr, "identifiers\t%lu (%.2f%%)\n",

+  fprintf (stderr, "\nlibcpp symtab string pool:\n");

+  fprintf (stderr, "\tidentifiers\t%lu (%.2f%%)\n",

 	   (unsigned long) nids, nids * 100.0 / nelts);
-  fprintf (stderr, "slots\t\t%lu\n",

-	   (unsigned long) table->nslots);

-  fprintf (stderr, "deleted\t\t%lu\n",

+  fprintf (stderr, "\tentries\t\t%lu (%.2f%%)\n",

+	   (unsigned long) nelts, nelts * 100.0 / table->nslots);

+  fprintf (stderr, "\tdeleted\t\t%lu\n",

 	   (unsigned long) deleted);
-  fprintf (stderr, "bytes\t\t%lu%c (%lu%c overhead)\n",

+  fprintf (stderr, "\tslots\t\t%u\n",

+	   table->nslots);

+  fprintf (stderr, "\tstring bytes\t%lu%c (%lu%c obstack_memory_used)\n",

 	   SCALE (total_bytes), LABEL (total_bytes),
-	   SCALE (overhead), LABEL (overhead));

-  fprintf (stderr, "table size\t%lu%c\n",

+	   SCALE (obmem), LABEL (obmem));

+  fprintf (stderr, "\ttable size\t%lu%c\n",

 	   SCALE (headers), LABEL (headers));
 
   exp_len = (double)total_bytes / (double)nelts;
   exp2_len = exp_len * exp_len;
   exp_len2 = (double) sum_of_squares / (double) nelts;
 
-  fprintf (stderr, "coll/search\t%.4f\n",

+  fprintf (stderr, "\texpansions\t%u\n",

+	   table->expands);

+  fprintf (stderr, "\tsearches\t%u\n",

+	   table->searches);

+  fprintf (stderr, "\tcollisions\t%u\n",

+	   table->collisions);

+  fprintf (stderr, "\tcoll/search\t%.4f\n",

 	   (double) table->collisions / (double) table->searches);
-  fprintf (stderr, "ins/search\t%.4f\n",

+  fprintf (stderr, "\tins/search\t%.4f\n",

 	   (double) nelts / (double) table->searches);
-  fprintf (stderr, "avg. entry\t%.2f bytes (+/- %.2f)\n",

+  fprintf (stderr, "\tavg. entry\t%.2f bytes (+/- %.2f)\n",

 	   exp_len, approx_sqrt (exp_len2 - exp2_len));
-  fprintf (stderr, "longest entry\t%lu\n",

+  fprintf (stderr, "\tlongest entry\t%lu\n",

 	   (unsigned long) longest);
 #undef SCALE
 #undef LABEL

=== modified file 'libiberty/hashtab.c'
--- libiberty/hashtab.c	2011-02-03 07:23:20 +0000

+++ libiberty/hashtab.c	2012-07-07 19:10:57 +0000

@@ -58,6 +58,7 @@  Boston, MA 02110-1301, USA.  */

 #endif
 
 #include <stdio.h>
+#include <assert.h>

 
 #include "libiberty.h"
 #include "ansidecl.h"
@@ -563,6 +564,7 @@  htab_expand (htab_t htab)

   htab->size_prime_index = nindex;
   htab->n_elements -= htab->n_deleted;
   htab->n_deleted = 0;
+  htab->expands++;

 
   p = oentries;
   do
@@ -812,6 +814,107 @@  htab_collisions (htab_t htab)

   return (double) htab->collisions / (double) htab->searches;
 }
 
+/* Return the number of expands */

+

+unsigned int

+htab_expands_num (htab_t htab)

+{

+  return htab->expands;

+}

+

+/* Return the number of collisions */

+

+unsigned int

+htab_collisions_num (htab_t htab)

+{

+  return htab->collisions;

+}

+

+/* Return the number of searches */

+

+unsigned int

+htab_searches_num (htab_t htab)

+{

+  return htab->searches;

+}

+

+/* Dump allocation statistics to stderr. If elem_size > 0 display total memory

+ * usage of hash table too. */

+

+void

+htab_dump_statistics (htab_t table, size_t elem_size)

+{

+  size_t n_valid, headers, contents, empties, deleted, total;

+  void **p, **limit;

+

+#define SCALE(x) ((unsigned long) ((x) < 1024*10 \

+		  ? (x) \

+		  : ((x) < 1024*1024*10 \

+		     ? (x) / 1024 \

+		     : (x) / (1024*1024))))

+#define LABEL(x) ((x) < 1024*10 ? ' ' : ((x) < 1024*1024*10 ? 'k' : 'M'))

+

+  deleted = n_valid = empties = 0;

+  p = table->entries;

+  limit = p + table->size;

+  do

+    if (*p == HTAB_DELETED_ENTRY)

+      ++deleted;

+    else if (*p == HTAB_EMPTY_ENTRY)

+      ++empties;

+    else

+      ++n_valid;

+  while (++p < limit);

+

+  assert (deleted == table->n_deleted);

+  assert (empties == table->size - table->n_elements);

+  assert (n_valid + deleted == table->n_elements);

+

+  headers = table->size * sizeof (*(table->entries));

+  contents = n_valid * elem_size;

+  total = sizeof (*table) + headers + contents;

+

+  fprintf (stderr, "\tslots\t\t%lu\n",

+	   (unsigned long) table->size);

+

+  fprintf (stderr, "\tused\t\t%lu (%.2f%%)\n",

+	   (unsigned long) table->n_elements,

+	   table->n_elements * 100.0 / table->size);

+  fprintf (stderr, "\t\tvalid\t\t%lu\n",

+	   (unsigned long) n_valid);

+  fprintf (stderr, "\t\tdeleted\t\t%lu\n",

+	   (unsigned long) table->n_deleted);

+

+  fprintf(stderr, "\ttotal size\t%lu %cB\n",

+	  SCALE (total), LABEL (total));

+  fprintf (stderr, "\t\tstruct htab\t%lu\t B\n",

+	   (unsigned long) sizeof (*table));

+  fprintf (stderr, "\t\ttable\t\t%lu\t%cB\n",

+	   SCALE (headers), LABEL (headers));

+  if (elem_size > 0)

+    {

+      fprintf (stderr, "\t\tone element\t%lu\t B\n",

+	       (unsigned long) elem_size);

+      fprintf (stderr, "\t\tall elements\t%lu\t%cB\n",

+	       SCALE (contents), LABEL (contents));

+    }

+  else

+      fprintf (stderr, "\t\tactual contents not included\n");

+

+  fprintf (stderr, "\texpansions\t%u\n",

+	   table->expands);

+  fprintf (stderr, "\tsearches\t%u\n",

+	   table->searches);

+  fprintf (stderr, "\tcollisions\t%u\n",

+	   table->collisions);

+  fprintf (stderr, "\tcoll/search\t%.4f\n",

+	   (double) table->collisions / (double) table->searches);

+

+#undef SCALE

+#undef LABEL

+}

+

+

 /* Hash P as a null-terminated string.
 
    Copied from gcc/hashtable.c.  Zack had the following to say with respect