From patchwork Sun Jul 8 05:31:46 2012 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Dimitrios Apostolou X-Patchwork-Id: 169621 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) by ozlabs.org (Postfix) with SMTP id 400732C0216 for ; Sun, 8 Jul 2012 15:32:35 +1000 (EST) Comment: DKIM? See http://www.dkim.org DKIM-Signature: v=1; a=rsa-sha1; c=relaxed/relaxed; d=gcc.gnu.org; s=default; x=1342330356; h=Comment: DomainKey-Signature:Received:Received:Received:Received:Received: Date:From:To:cc:Subject:Message-ID:User-Agent:MIME-Version: Content-Type:Mailing-List:Precedence:List-Id:List-Unsubscribe: List-Archive:List-Post:List-Help:Sender:Delivered-To; bh=50yKDJg bxme4rR7WqZqwLGTLn30=; b=faJBDGnASREaRTCLiUB7VvEM1tnYj2DvrJlejKm n+HkEmoQOGCGmBmEWZ/O6EUlYw4YrPRO4mOB97sj/mM/Nb+ZquAmRKmkfkX7+KAk 2whlJhJLHhqqeuhcDg6k4/kEFa0HqZ+YXkT8qSWzn0OkJnzcEh8uVG7NCk9MpL/w N3Ck= Comment: DomainKeys? See http://antispam.yahoo.com/domainkeys DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=default; d=gcc.gnu.org; h=Received:Received:X-SWARE-Spam-Status:X-Spam-Check-By:Received:Received:Received:Date:From:To:cc:Subject:Message-ID:User-Agent:MIME-Version:Content-Type:X-IsSubscribed:Mailing-List:Precedence:List-Id:List-Unsubscribe:List-Archive:List-Post:List-Help:Sender:Delivered-To; b=RZPesOr18EUKGByYhS/mc76WGbFPWVnul1444MKbRz+nJpSD2LxP1CZt53m4/S ZgQ4JBnEtNKTsdbENW5vGblvB9i7wbfU2+RPkII259UM6b1R2H6a2TRlAZCOJrVX beAyXGjZR9khHVxNfAztQSy9aoTB8LfQMAMsZzKSsJ0DM=; Received: (qmail 28858 invoked by alias); 8 Jul 2012 05:32:29 -0000 Received: (qmail 28842 invoked by uid 22791); 8 Jul 2012 05:32:24 -0000 X-SWARE-Spam-Status: No, hits=0.9 required=5.0 tests=AWL, BAYES_50, FREEMAIL_FROM, KAM_STOCKGEN, MALFORMED_FREEMAIL, RCVD_IN_DNSWL_NONE, RCVD_IN_HOSTKARMA_NO, RCVD_IN_HOSTKARMA_YE, RDNS_NONE X-Spam-Check-By: sourceware.org Received: from Unknown (HELO mailout-de.gmx.net) (213.165.64.22) by sourceware.org (qpsmtpd/0.43rc1) with SMTP; Sun, 08 Jul 2012 05:31:57 +0000 Received: (qmail invoked by alias); 08 Jul 2012 05:31:49 -0000 Received: from teras.ics.forth.gr (EHLO teras.ics.forth.gr) [139.91.70.93] by mail.gmx.net (mp034) with SMTP; 08 Jul 2012 07:31:49 +0200 Date: Sun, 8 Jul 2012 08:31:46 +0300 (EEST) From: Dimitrios Apostolou To: gcc-patches@gcc.gnu.org cc: Jan Hubicka , Andrey Belevantsev Subject: ping again - Show hash table stats when -fmem-report Message-ID: User-Agent: Alpine 2.02 (LNX 1266 2009-07-14) MIME-Version: 1.0 X-IsSubscribed: yes Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org 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 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 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. === 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 +#include #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