[Committed] Use special-purpose hash table to speed up walk_tree

[Committed] Use special-purpose hash table to speed up walk_tree

[Matt Austern]

This patch isn't really as big as it looks.  walk_tree allows you to 
provide a hash table to keep track of which nodes have already been 
seen.  We were using htab_t, a general-purpose hash table with lots of 
knobs for the client to tweak.  This patch replaces it with a 
special-purpose hash table that has no more functionality than 
walk_tree needs.  In particular, this special-purpose hash table 
doesn't support deletion, doesn't give its client control over resizing 
policy, and doesn't allow its client to specify the hash function or 
equality function.  (It just uses the values of the pointers 
themselves.)

Bootstrapped and tested (C, C++, Java) on powerpc-apple-darwin.  This 
gives a 2% speedup on building QT.

Approved by Mark Mitchell offline.

			--Matt

Index: ChangeLog
===================================================================
RCS file: /cvs/gcc/gcc/gcc/ChangeLog,v
retrieving revision 2.5888
diff -p -r2.5888 ChangeLog
*** ChangeLog	14 Oct 2004 22:30:37 -0000	2.5888
--- ChangeLog	14 Oct 2004 23:06:05 -0000
***************
*** 1,3 ****
--- 1,27 ----
+ 2004-10-14  Matt Austern  <austern@apple.com>
+
+ 	* pointer-set.c: New file, special-purpose hash table.
+ 	* pointer-set.h: New file.
+ 	* tree.h (struct pointer_set_t): Declare as opaque type.
+ 	(tree_walk): Last argument is pointer_set_t* now.
+ 	* tree-inline.c (WALK_SUBTREE): Convert from htab to pset.
+ 	(walk_type_fields):
+ 	(walk_tree): Convert from htab_t to pointer_set_t for keeping
+ 	track of which nodes have already been visited.
+ 	(walk_tree_without_duplicates): Convert from htab_t to pointer_set_t.
+ 	* cgraphunit.c (cgraph_create_edges): Likewise.
+ 	(cgraph_characterize_statics_local): Likewise.
+ 	* tree-dfa.c (collect_dfa_stats): Likewise.
+ 	* langhooks-def.h (lhd_tree_inlining_walk_subtrees): Last arg is
+ 	pointer_set_t* now.
+ 	* langhooks.c (lhd_tree_inlining_walk_subtrees): Likewise.
+ 	* langhooks.h (struct lang_hooks_for_tree_inlining): Last arg type
+ 	of walk_subtrees is pointer_set_t* now.
+ 	* Makefile.in (OBJS-common): add pointer-set.o
+ 	(tree-inline.o): Depends on pointer-set.h
+ 	(tree-dfa.o): Likewise
+ 	(cgraphunit.o): Likewise
+ 	
   2004-10-14  Geoffrey Keating  <geoffk@apple.com>

   	* config/rs6000/darwin.h (ASM_SPEC): Delete.
Index: Makefile.in
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Makefile.in,v
retrieving revision 1.1410
diff -p -r1.1410 Makefile.in
*** Makefile.in	13 Oct 2004 03:48:01 -0000	1.1410
--- Makefile.in	14 Oct 2004 23:06:05 -0000
*************** OBJS-common = \
*** 914,920 ****
    params.o postreload.o postreload-gcse.o predict.o			   \
    insn-preds.o integrate.o intl.o jump.o langhooks.o lcm.o lists.o 	   
\
    local-alloc.o loop.o modulo-sched.o optabs.o options.o opts.o		   \
!  params.o postreload.o postreload-gcse.o predict.o			   \
    print-rtl.o print-tree.o value-prof.o var-tracking.o			   \
    profile.o ra.o ra-build.o ra-colorize.o ra-debug.o ra-rewrite.o	   \
    real.o recog.o reg-stack.o regclass.o regmove.o regrename.o		   \
--- 914,920 ----
    params.o postreload.o postreload-gcse.o predict.o			   \
    insn-preds.o integrate.o intl.o jump.o langhooks.o lcm.o lists.o 	   
\
    local-alloc.o loop.o modulo-sched.o optabs.o options.o opts.o		   \
!  params.o pointer-set.o postreload.o postreload-gcse.o predict.o 	   \
    print-rtl.o print-tree.o value-prof.o var-tracking.o			   \
    profile.o ra.o ra-build.o ra-colorize.o ra-debug.o ra-rewrite.o	   \
    real.o recog.o reg-stack.o regclass.o regmove.o regrename.o		   \
*************** tree-inline.o : tree-inline.c $(CONFIG_H
*** 1592,1598 ****
      $(TREE_H) $(RTL_H) $(EXPR_H) $(FLAGS_H) $(PARAMS_H) input.h 
insn-config.h \
      $(INTEGRATE_H) $(VARRAY_H) $(HASHTAB_H) $(SPLAY_TREE_H) toplev.h \
      langhooks.h $(C_COMMON_H) tree-inline.h $(CGRAPH_H) intl.h 
function.h \
!    $(TREE_GIMPLE_H)
   print-tree.o : print-tree.c $(CONFIG_H) $(SYSTEM_H) coretypes.h 
$(TM_H) $(TREE_H) \
      $(GGC_H) langhooks.h real.h
   stor-layout.o : stor-layout.c $(CONFIG_H) $(SYSTEM_H) coretypes.h 
$(TM_H) \
--- 1592,1598 ----
      $(TREE_H) $(RTL_H) $(EXPR_H) $(FLAGS_H) $(PARAMS_H) input.h 
insn-config.h \
      $(INTEGRATE_H) $(VARRAY_H) $(HASHTAB_H) $(SPLAY_TREE_H) toplev.h \
      langhooks.h $(C_COMMON_H) tree-inline.h $(CGRAPH_H) intl.h 
function.h \
!    pointer-set.h $(TREE_GIMPLE_H)
   print-tree.o : print-tree.c $(CONFIG_H) $(SYSTEM_H) coretypes.h 
$(TM_H) $(TREE_H) \
      $(GGC_H) langhooks.h real.h
   stor-layout.o : stor-layout.c $(CONFIG_H) $(SYSTEM_H) coretypes.h 
$(TM_H) \
*************** tree-iterator.o : tree-iterator.c $(CONF
*** 1686,1692 ****
      coretypes.h $(GGC_H) tree-iterator.h tree-gimple.h 
gt-tree-iterator.h
   tree-dfa.o : tree-dfa.c $(TREE_FLOW_H) $(CONFIG_H) $(SYSTEM_H) \
      $(RTL_H) $(TREE_H) $(TM_P_H) $(EXPR_H) $(GGC_H) output.h 
diagnostic.h \
!    errors.h tree-inline.h $(HASHTAB_H) $(FLAGS_H) function.h 
$(TIMEVAR_H) \
      convert.h $(TM_H) coretypes.h langhooks.h \
      $(TREE_DUMP_H) tree-pass.h params.h $(CGRAPH_H)
   tree-ssa-operands.o : tree-ssa-operands.c $(TREE_FLOW_H) $(CONFIG_H) \
--- 1686,1692 ----
      coretypes.h $(GGC_H) tree-iterator.h tree-gimple.h 
gt-tree-iterator.h
   tree-dfa.o : tree-dfa.c $(TREE_FLOW_H) $(CONFIG_H) $(SYSTEM_H) \
      $(RTL_H) $(TREE_H) $(TM_P_H) $(EXPR_H) $(GGC_H) output.h 
diagnostic.h \
!    errors.h tree-inline.h $(HASHTAB_H) pointer-set.h $(FLAGS_H) 
function.h $(TIMEVAR_H) \
      convert.h $(TM_H) coretypes.h langhooks.h \
      $(TREE_DUMP_H) tree-pass.h params.h $(CGRAPH_H)
   tree-ssa-operands.o : tree-ssa-operands.c $(TREE_FLOW_H) $(CONFIG_H) \
*************** cgraph.o : cgraph.c $(CONFIG_H) $(SYSTEM
*** 1923,1929 ****
      output.h intl.h
   cgraphunit.o : cgraphunit.c $(CONFIG_H) $(SYSTEM_H) coretypes.h 
$(TM_H) $(TREE_H) \
      langhooks.h tree-inline.h toplev.h $(FLAGS_H) $(GGC_H)  
$(TARGET_H) $(CGRAPH_H) intl.h \
!    function.h $(TREE_GIMPLE_H) $(TREE_FLOW_H)
   coverage.o : coverage.c gcov-io.c $(CONFIG_H) $(SYSTEM_H) coretypes.h 
\
      $(TM_H) $(RTL_H) $(TREE_H) $(FLAGS_H) output.h $(REGS_H) $(EXPR_H) 
function.h \
      toplev.h $(GGC_H) $(TARGET_H) langhooks.h $(COVERAGE_H) libfuncs.h 
\
--- 1923,1929 ----
      output.h intl.h
   cgraphunit.o : cgraphunit.c $(CONFIG_H) $(SYSTEM_H) coretypes.h 
$(TM_H) $(TREE_H) \
      langhooks.h tree-inline.h toplev.h $(FLAGS_H) $(GGC_H)  
$(TARGET_H) $(CGRAPH_H) intl.h \
!    pointer-set.h function.h $(TREE_GIMPLE_H) $(TREE_FLOW_H)
   coverage.o : coverage.c gcov-io.c $(CONFIG_H) $(SYSTEM_H) coretypes.h 
\
      $(TM_H) $(RTL_H) $(TREE_H) $(FLAGS_H) output.h $(REGS_H) $(EXPR_H) 
function.h \
      toplev.h $(GGC_H) $(TARGET_H) langhooks.h $(COVERAGE_H) libfuncs.h 
\
*************** lambda-code.o: lambda-code.c $(LAMBDA_H)
*** 2172,2177 ****
--- 2172,2178 ----
      $(TREE_FLOW_H) $(TREE_DUMP_H) $(TIMEVAR_H) cfgloop.h \
      $(TREE_DATA_REF_H) $(SCEV_H)
   params.o : params.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) 
$(PARAMS_H) toplev.h
+ pointer-set.o: pointer-set.c pointer-set.h $(CONFIG_H) $(SYSTEM_H)
   hooks.o: hooks.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) 
$(HOOKS_H)
   pretty-print.o: $(CONFIG_H) $(SYSTEM_H) coretypes.h intl.h 
$(PRETTY_PRINT_H) \
      $(TREE_H)
Index: cgraphunit.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cgraphunit.c,v
retrieving revision 1.86
diff -p -r1.86 cgraphunit.c
*** cgraphunit.c	1 Oct 2004 15:11:10 -0000	1.86
--- cgraphunit.c	14 Oct 2004 23:06:06 -0000
*************** Software Foundation, 59 Temple Place - S
*** 186,192 ****
   #include "tree-flow.h"
   #include "tree-inline.h"
   #include "langhooks.h"
! #include "hashtab.h"
   #include "toplev.h"
   #include "flags.h"
   #include "ggc.h"
--- 186,192 ----
   #include "tree-flow.h"
   #include "tree-inline.h"
   #include "langhooks.h"
! #include "pointer-set.h"
   #include "toplev.h"
   #include "flags.h"
   #include "ggc.h"
*************** static int overall_insns;
*** 223,229 ****
      walk_tree_without_duplicates doesn't guarantee each node is visited
      once because it gets a new htab upon each recursive call from
      record_calls_1.  */
! static htab_t visited_nodes;

   static FILE *cgraph_dump_file;

--- 223,229 ----
      walk_tree_without_duplicates doesn't guarantee each node is visited
      once because it gets a new htab upon each recursive call from
      record_calls_1.  */
! static struct pointer_set_t *visited_nodes;

   static FILE *cgraph_dump_file;

*************** cgraph_create_edges (struct cgraph_node
*** 698,707 ****
   {
     /* The nodes we're interested in are never shared, so walk
        the tree ignoring duplicates.  */
!   visited_nodes = htab_create (37, htab_hash_pointer,
! 				    htab_eq_pointer, NULL);
     walk_tree (&body, record_call_1, node, visited_nodes);
!   htab_delete (visited_nodes);
     visited_nodes = NULL;
   }

--- 698,706 ----
   {
     /* The nodes we're interested in are never shared, so walk
        the tree ignoring duplicates.  */
!   visited_nodes = pointer_set_create ();
     walk_tree (&body, record_call_1, node, visited_nodes);
!   pointer_set_destroy (visited_nodes);
     visited_nodes = NULL;
   }

*************** cgraph_characterize_statics_local (struc
*** 2288,2295 ****

     /* The nodes we're interested in are never shared, so walk
        the tree ignoring duplicates.  */
!   visited_nodes = htab_create (37, htab_hash_pointer,
! 			       htab_eq_pointer, NULL);

     /* FIXME -- PROFILE-RESTRUCTURE: Remove creation of _decl_uid vars. 
  */
     l->statics_read_by_decl_uid = BITMAP_GGC_ALLOC ();
--- 2287,2293 ----

     /* The nodes we're interested in are never shared, so walk
        the tree ignoring duplicates.  */
!   visited_nodes = pointer_set_create ();

     /* FIXME -- PROFILE-RESTRUCTURE: Remove creation of _decl_uid vars. 
  */
     l->statics_read_by_decl_uid = BITMAP_GGC_ALLOC ();
*************** cgraph_characterize_statics_local (struc
*** 2299,2305 ****
       fprintf (cgraph_dump_file, "\n local analysis of %s", 
cgraph_node_name (fn));

     walk_tree (&DECL_SAVED_TREE (decl), scan_for_static_refs, fn, 
visited_nodes);
!   htab_delete (visited_nodes);
     visited_nodes = NULL;
   }

--- 2297,2303 ----
       fprintf (cgraph_dump_file, "\n local analysis of %s", 
cgraph_node_name (fn));

     walk_tree (&DECL_SAVED_TREE (decl), scan_for_static_refs, fn, 
visited_nodes);
!   pointer_set_destroy (visited_nodes);
     visited_nodes = NULL;
   }

Index: langhooks-def.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/langhooks-def.h,v
retrieving revision 1.93
diff -p -r1.93 langhooks-def.h
*** langhooks-def.h	15 Sep 2004 17:02:55 -0000	1.93
--- langhooks-def.h	14 Oct 2004 23:06:06 -0000
*************** extern size_t lhd_tree_size (enum tree_c
*** 73,79 ****

   /* Declarations of default tree inlining hooks.  */
   extern tree lhd_tree_inlining_walk_subtrees (tree *, int *, 
walk_tree_fn,
! 					     void *, void *);
   extern int lhd_tree_inlining_cannot_inline_tree_fn (tree *);
   extern int lhd_tree_inlining_disregard_inline_limits (tree);
   extern tree lhd_tree_inlining_add_pending_fn_decls (void *, tree);
--- 73,79 ----

   /* Declarations of default tree inlining hooks.  */
   extern tree lhd_tree_inlining_walk_subtrees (tree *, int *, 
walk_tree_fn,
! 					     void *, struct pointer_set_t*);
   extern int lhd_tree_inlining_cannot_inline_tree_fn (tree *);
   extern int lhd_tree_inlining_disregard_inline_limits (tree);
   extern tree lhd_tree_inlining_add_pending_fn_decls (void *, tree);
Index: langhooks.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/langhooks.c,v
retrieving revision 1.78
diff -p -r1.78 langhooks.c
*** langhooks.c	17 Sep 2004 21:54:35 -0000	1.78
--- langhooks.c	14 Oct 2004 23:06:06 -0000
*************** lhd_tree_inlining_walk_subtrees (tree *t
*** 298,304 ****
   				 int *subtrees ATTRIBUTE_UNUSED,
   				 walk_tree_fn func ATTRIBUTE_UNUSED,
   				 void *data ATTRIBUTE_UNUSED,
! 				 void *htab ATTRIBUTE_UNUSED)
   {
     return NULL_TREE;
   }
--- 298,304 ----
   				 int *subtrees ATTRIBUTE_UNUSED,
   				 walk_tree_fn func ATTRIBUTE_UNUSED,
   				 void *data ATTRIBUTE_UNUSED,
! 				 struct pointer_set_t *pset ATTRIBUTE_UNUSED)
   {
     return NULL_TREE;
   }
Index: langhooks.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/langhooks.h,v
retrieving revision 1.101
diff -p -r1.101 langhooks.h
*** langhooks.h	17 Sep 2004 21:54:35 -0000	1.101
--- langhooks.h	14 Oct 2004 23:06:06 -0000
*************** struct lang_hooks_for_tree_inlining
*** 35,41 ****
   {
     tree (*walk_subtrees) (tree *, int *,
   			 tree (*) (tree *, int *, void *),
! 			 void *, void *);
     int (*cannot_inline_tree_fn) (tree *);
     int (*disregard_inline_limits) (tree);
     tree (*add_pending_fn_decls) (void *, tree);
--- 35,41 ----
   {
     tree (*walk_subtrees) (tree *, int *,
   			 tree (*) (tree *, int *, void *),
! 			 void *, struct pointer_set_t*);
     int (*cannot_inline_tree_fn) (tree *);
     int (*disregard_inline_limits) (tree);
     tree (*add_pending_fn_decls) (void *, tree);
Index: pointer-set.c
===================================================================
RCS file: pointer-set.c
diff -N pointer-set.c
*** /dev/null	1 Jan 1970 00:00:00 -0000
--- pointer-set.c	14 Oct 2004 23:06:06 -0000
***************
*** 0 ****
--- 1,167 ----
+ /* Set operations on pointers
+    Copyright (C) 2004 Free Software Foundation, Inc.
+
+ This file is part of GCC.
+
+ GCC is free software; you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published by
+ the Free Software Foundation; either version 2, or (at your option)
+ any later version.
+
+ GCC is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with GCC; see the file COPYING.  If not, write to
+ the Free Software Foundation, 59 Temple Place - Suite 330,
+ Boston, MA 02111-1307, USA.  */
+
+ #include "config.h"
+ #include "system.h"
+ #include "pointer-set.h"
+
+ /* A pointer sets is represented as a simple open-addressing hash
+    table.  Simplifications: The hash code is based on the value of the
+    pointer, not what it points to.  The number of buckets is always a
+    power of 2.  Null pointers are a reserved value.  Deletion is not
+    supported.  There is no mechanism for user control of hash
+    function, equality comparison, initial size, or resizing policy.
+ */
+
+ struct pointer_set_t
+ {
+   size_t log_slots;
+   size_t n_slots;		/* n_slots = 2^log_slots */
+   size_t n_elements;
+
+   void **slots;
+ };
+
+ /* Use the multiplicative method, as described in Knuth 6.4, to obtain
+    a hash code for P in the range [0, MAX).  MAX == 2^LOGMAX.
+
+    Summary of this method: Multiply p by some number A that's
+    relatively prime to 2^sizeof(size_t).  The result is two words.
+    Discard the most significant word, and return the most significant
+    N bits of the least significant word.  As suggested by Knuth, our
+    choice for A is the integer part of 2^32 / phi, where phi is the
+    golden ratio.
+
+    We don't need to do anything special for full-width multiplication
+    because we're only interested in the least significant word of the
+    product, and unsigned arithmetic in C is modulo the word size. */
+
+ static inline size_t
+ hash1 (const void *p, unsigned long max, unsigned long logmax)
+ {
+   const unsigned long A = 0x9e3779b9u;
+   const unsigned long shift = sizeof(unsigned long) * CHAR_BIT - 
logmax;
+
+   return ((A * (unsigned long) p) >> shift) & (max - 1);
+ }
+
+ /* Allocate an empty pointer set. */
+ struct pointer_set_t *
+ pointer_set_create (void)
+ {
+   struct pointer_set_t *result = XNEW (struct pointer_set_t);
+
+   result->n_elements = 0;
+   result->log_slots = 8;
+   result->n_slots = (size_t) 1 << result->log_slots;
+
+   result->slots = XCNEWVEC (void *, result->n_slots);
+   return result;
+ }
+
+ /* Reclaims all memory associated with PSET. */
+ void pointer_set_destroy (struct pointer_set_t *pset)
+ {
+   XDELETEVEC (pset->slots);
+   XDELETE (pset);
+ }
+
+ /* Returns nonzero if PSET contains P.  P must be nonnull.
+
+    Collisions are resolved by linear probing.  More complicated
+    collision management schemes are only useful when the load factor
+    significatly exceeds 0.5, and we never let that happen. */
+ int
+ pointer_set_contains (struct pointer_set_t *pset, void *p)
+ {
+   size_t n = hash1 (p, pset->n_slots, pset->log_slots);
+
+   while (true)
+     {
+       if (pset->slots[n] == p)
+ 	return 1;
+       else if (pset->slots[n] == 0)
+ 	return 0;
+       else
+ 	{
+ 	  ++n;
+ 	  if (n == pset->n_slots)
+ 	    n = 0;
+ 	}
+     }
+ }
+
+ /* Subroutine of pointer_set_insert.  Inserts P into an empty
+    element of SLOTS, an array of length N_SLOTS.  Returns nonzero
+    if P was already present in N_SLOTS. */
+ static int
+ insert_aux (void *p, void **slots, size_t n_slots, size_t log_slots)
+ {
+   size_t n = hash1 (p, n_slots, log_slots);
+   while (true)
+     {
+       if (slots[n] == p)
+ 	return 1;
+       else if (slots[n] == 0)
+ 	{
+ 	  slots[n] = p;
+ 	  return 0;
+ 	}
+       else
+ 	{
+ 	  ++n;
+ 	  if (n == n_slots)
+ 	    n = 0;
+ 	}
+     }
+ }
+
+ /* Inserts P into PSET if it wasn't already there.  Returns nonzero
+    if it was already there. P must be nonnull. */
+ int
+ pointer_set_insert (struct pointer_set_t *pset, void *p)
+ {
+   if (insert_aux (p, pset->slots, pset->n_slots, pset->log_slots))
+     return 1;
+
+   /* We've inserted a new element.  Expand the table if necessary to 
keep
+      the load factor small. */
+   ++pset->n_elements;
+   if (pset->n_elements > pset->n_slots / 4)
+     {
+       size_t new_log_slots = pset->log_slots + 1;
+       size_t new_n_slots = pset->n_slots * 2;
+       void **new_slots = XCNEWVEC (void *, new_n_slots);
+       size_t i;
+
+       for (i = 0; i < pset->n_slots; ++i)
+ 	{
+ 	  if (pset->slots[i])
+ 	    insert_aux (pset->slots[i], new_slots, new_n_slots, 
new_log_slots);
+ 	}
+
+       XDELETEVEC (pset->slots);
+       pset->n_slots = new_n_slots;
+       pset->log_slots = new_log_slots;
+       pset->slots = new_slots;
+     }
+
+   return 0;
+ }
Index: pointer-set.h
===================================================================
RCS file: pointer-set.h
diff -N pointer-set.h
*** /dev/null	1 Jan 1970 00:00:00 -0000
--- pointer-set.h	14 Oct 2004 23:06:06 -0000
***************
*** 0 ****
--- 1,32 ----
+ /* Set operations on pointers
+    Copyright (C) 2004 Free Software Foundation, Inc.
+
+ This file is part of GCC.
+
+ GCC is free software; you can redistribute it and/or modify it under
+ the terms of the GNU General Public License as published by the Free
+ Software Foundation; either version 2, or (at your option) any later
+ version.
+
+ GCC is distributed in the hope that it will be useful, but WITHOUT ANY
+ WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with GCC; see the file COPYING.  If not, write to the Free
+ Software Foundation, 59 Temple Place - Suite 330, Boston, MA
+ 02111-1307, USA.  */
+
+ #ifndef POINTER_SET_H
+ #define POINTER_SET_H
+
+ struct pointer_set_t;
+
+ struct pointer_set_t *pointer_set_create (void);
+ void pointer_set_destroy (struct pointer_set_t *pset);
+
+ int pointer_set_contains (struct pointer_set_t *pset, void *p);
+ int pointer_set_insert (struct pointer_set_t *pset, void *p);
+
+ #endif  /* POINTER_SET_H  */
Index: tree-dfa.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-dfa.c,v
retrieving revision 2.36
diff -p -r2.36 tree-dfa.c
*** tree-dfa.c	30 Sep 2004 14:09:37 -0000	2.36
--- tree-dfa.c	14 Oct 2004 23:06:06 -0000
*************** Boston, MA 02111-1307, USA.  */
*** 24,29 ****
--- 24,30 ----
   #include "coretypes.h"
   #include "tm.h"
   #include "hashtab.h"
+ #include "pointer-set.h"
   #include "tree.h"
   #include "rtl.h"
   #include "tm_p.h"
*************** debug_dfa_stats (void)
*** 759,765 ****
   static void
   collect_dfa_stats (struct dfa_stats_d *dfa_stats_p)
   {
!   htab_t htab;
     basic_block bb;
     block_stmt_iterator i;

--- 760,766 ----
   static void
   collect_dfa_stats (struct dfa_stats_d *dfa_stats_p)
   {
!   struct pointer_set_t *pset;
     basic_block bb;
     block_stmt_iterator i;

*************** collect_dfa_stats (struct dfa_stats_d *d
*** 769,781 ****

     /* Walk all the trees in the function counting references.  Start at
        basic block 0, but don't stop at block boundaries.  */
!   htab = htab_create (30, htab_hash_pointer, htab_eq_pointer, NULL);

     for (i = bsi_start (BASIC_BLOCK (0)); !bsi_end_p (i); bsi_next (&i))
       walk_tree (bsi_stmt_ptr (i), collect_dfa_stats_r, (void *) 
dfa_stats_p,
! 	       (void *) htab);

!   htab_delete (htab);

     FOR_EACH_BB (bb)
       {
--- 770,782 ----

     /* Walk all the trees in the function counting references.  Start at
        basic block 0, but don't stop at block boundaries.  */
!   pset = pointer_set_create ();

     for (i = bsi_start (BASIC_BLOCK (0)); !bsi_end_p (i); bsi_next (&i))
       walk_tree (bsi_stmt_ptr (i), collect_dfa_stats_r, (void *) 
dfa_stats_p,
! 	       pset);

!   pointer_set_destroy (pset);

     FOR_EACH_BB (bb)
       {
Index: tree-inline.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-inline.c,v
retrieving revision 1.145
diff -p -r1.145 tree-inline.c
*** tree-inline.c	7 Oct 2004 08:36:15 -0000	1.145
--- tree-inline.c	14 Oct 2004 23:06:06 -0000
*************** Boston, MA 02111-1307, USA.  */
*** 35,40 ****
--- 35,41 ----
   #include "integrate.h"
   #include "varray.h"
   #include "hashtab.h"
+ #include "pointer-set.h"
   #include "splay-tree.h"
   #include "langhooks.h"
   #include "cgraph.h"
*************** save_body (tree fn, tree *arg_copy, tree
*** 1877,1883 ****
   #define WALK_SUBTREE(NODE)				\
     do							\
       {							\
!       result = walk_tree (&(NODE), func, data, htab);	\
         if (result)					\
   	return result;					\
       }							\
--- 1878,1884 ----
   #define WALK_SUBTREE(NODE)				\
     do							\
       {							\
!       result = walk_tree (&(NODE), func, data, pset);	\
         if (result)					\
   	return result;					\
       }							\
*************** save_body (tree fn, tree *arg_copy, tree
*** 1888,1894 ****
      value are as for walk_tree.  */

   static tree
! walk_type_fields (tree type, walk_tree_fn func, void *data, void 
*htab)
   {
     tree result = NULL_TREE;

--- 1889,1896 ----
      value are as for walk_tree.  */

   static tree
! walk_type_fields (tree type, walk_tree_fn func, void *data,
! 		  struct pointer_set_t *pset)
   {
     tree result = NULL_TREE;

*************** walk_type_fields (tree type, walk_tree_f
*** 1906,1912 ****
         if (POINTER_TYPE_P (TREE_TYPE (type))
   	  && POINTER_TYPE_P (TREE_TYPE (TREE_TYPE (type)))
   	  && POINTER_TYPE_P (TREE_TYPE (TREE_TYPE (TREE_TYPE (type))))
! 	  && !htab)
   	{
   	  result = walk_tree_without_duplicates (&TREE_TYPE (type),
   						 func, data);
--- 1908,1914 ----
         if (POINTER_TYPE_P (TREE_TYPE (type))
   	  && POINTER_TYPE_P (TREE_TYPE (TREE_TYPE (type)))
   	  && POINTER_TYPE_P (TREE_TYPE (TREE_TYPE (TREE_TYPE (type))))
! 	  && !pset)
   	{
   	  result = walk_tree_without_duplicates (&TREE_TYPE (type),
   						 func, data);
*************** walk_type_fields (tree type, walk_tree_f
*** 1971,1983 ****
   /* Apply FUNC to all the sub-trees of TP in a pre-order traversal.  
FUNC is
      called with the DATA and the address of each sub-tree.  If FUNC 
returns a
      non-NULL value, the traversal is aborted, and the value returned 
by FUNC
!    is returned.  If HTAB is non-NULL it is used to record the nodes 
visited,
      and to avoid visiting a node more than once.  */

   tree
! walk_tree (tree *tp, walk_tree_fn func, void *data, void *htab_)
   {
-   htab_t htab = (htab_t) htab_;
     enum tree_code code;
     int walk_subtrees;
     tree result;
--- 1973,1984 ----
   /* Apply FUNC to all the sub-trees of TP in a pre-order traversal.  
FUNC is
      called with the DATA and the address of each sub-tree.  If FUNC 
returns a
      non-NULL value, the traversal is aborted, and the value returned 
by FUNC
!    is returned.  If PSET is non-NULL it is used to record the nodes 
visited,
      and to avoid visiting a node more than once.  */

   tree
! walk_tree (tree *tp, walk_tree_fn func, void *data, struct 
pointer_set_t *pset)
   {
     enum tree_code code;
     int walk_subtrees;
     tree result;
*************** walk_tree (tree *tp, walk_tree_fn func,
*** 1995,2011 ****
     if (!*tp)
       return NULL_TREE;

!   if (htab)
!     {
!       void **slot;
!
!       /* Don't walk the same tree twice, if the user has requested
!          that we avoid doing so.  */
!       slot = htab_find_slot (htab, *tp, INSERT);
!       if (*slot)
! 	return NULL_TREE;
!       *slot = *tp;
!     }

     /* Call the function.  */
     walk_subtrees = 1;
--- 1996,2005 ----
     if (!*tp)
       return NULL_TREE;

!   /* Don't walk the same tree twice, if the user has requested
!      that we avoid doing so.  */
!   if (pset && pointer_set_insert (pset, *tp))
!     return NULL_TREE;

     /* Call the function.  */
     walk_subtrees = 1;
*************** walk_tree (tree *tp, walk_tree_fn func,
*** 2029,2035 ****
       }

     result = lang_hooks.tree_inlining.walk_subtrees (tp, 
&walk_subtrees, func,
! 						   data, htab);
     if (result || ! walk_subtrees)
       return result;

--- 2023,2029 ----
       }

     result = lang_hooks.tree_inlining.walk_subtrees (tp, 
&walk_subtrees, func,
! 						   data, pset);
     if (result || ! walk_subtrees)
       return result;

*************** walk_tree (tree *tp, walk_tree_fn func,
*** 2053,2059 ****
         if (result || !walk_subtrees)
   	return NULL_TREE;

!       result = walk_type_fields (*type_p, func, data, htab_);
         if (result)
   	return result;

--- 2047,2053 ----
         if (result || !walk_subtrees)
   	return NULL_TREE;

!       result = walk_type_fields (*type_p, func, data, pset);
         if (result)
   	return result;

*************** walk_tree (tree *tp, walk_tree_fn func,
*** 2124,2130 ****
     /* If this is a type, walk the needed fields in the type.  */
     else if (TYPE_P (*tp))
       {
!       result = walk_type_fields (*tp, func, data, htab_);
         if (result)
   	return result;
       }
--- 2118,2124 ----
     /* If this is a type, walk the needed fields in the type.  */
     else if (TYPE_P (*tp))
       {
!       result = walk_type_fields (*tp, func, data, pset);
         if (result)
   	return result;
       }
*************** tree
*** 2227,2237 ****
   walk_tree_without_duplicates (tree *tp, walk_tree_fn func, void *data)
   {
     tree result;
!   htab_t htab;

!   htab = htab_create (37, htab_hash_pointer, htab_eq_pointer, NULL);
!   result = walk_tree (tp, func, data, htab);
!   htab_delete (htab);
     return result;
   }

--- 2221,2231 ----
   walk_tree_without_duplicates (tree *tp, walk_tree_fn func, void *data)
   {
     tree result;
!   struct pointer_set_t *pset;

!   pset = pointer_set_create ();
!   result = walk_tree (tp, func, data, pset);
!   pointer_set_destroy (pset);
     return result;
   }

Index: tree.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree.h,v
retrieving revision 1.638
diff -p -r1.638 tree.h
*** tree.h	14 Oct 2004 16:44:43 -0000	1.638
--- tree.h	14 Oct 2004 23:06:06 -0000
*************** extern void dwarf2out_return_reg (const
*** 3790,3799 ****

   /* In tree-inline.c  */

   /* The type of a callback function for walking over tree structure.  
*/

   typedef tree (*walk_tree_fn) (tree *, int *, void *);
! extern tree walk_tree (tree*, walk_tree_fn, void*, void*);
   extern tree walk_tree_without_duplicates (tree*, walk_tree_fn, void*);

   /* In tree-dump.c */
--- 3790,3803 ----

   /* In tree-inline.c  */

+ /* The type of a set of already-visited pointers.  Functions for 
creating
+    and manipulating it are declared in pointer-set.h */
+ struct pointer_set_t;
+
   /* The type of a callback function for walking over tree structure.  
*/

   typedef tree (*walk_tree_fn) (tree *, int *, void *);
! extern tree walk_tree (tree*, walk_tree_fn, void*, struct 
pointer_set_t*);
   extern tree walk_tree_without_duplicates (tree*, walk_tree_fn, void*);

   /* In tree-dump.c */
Index: cp/ChangeLog
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cp/ChangeLog,v
retrieving revision 1.4432
diff -p -r1.4432 ChangeLog
*** cp/ChangeLog	13 Oct 2004 17:18:08 -0000	1.4432
--- cp/ChangeLog	14 Oct 2004 23:06:07 -0000
***************
*** 1,3 ****
--- 1,11 ----
+ 2004-10-14  Matt Austern  <austern@apple.com>
+
+ 	* Make-lang.in (pt.o): depends on pointer-set.h
+ 	* cp-tree.h (cp_walk_subtrees): Last argument is pointer_set_t*	now.
+ 	* pt.c (struct pair_fn_data): Use pointer_set_t, not htab_t
+ 	(for_each_template_parm): Convert from htab_t to pointer_set_t.
+ 	* tree.c (cp_walk_subtrees): Last argument is pointer_set_t* now.
+ 	
   2004-10-13  Andrew Pinski  <pinskia@physics.uc.edu>

   	PR c++/17661
Index: cp/Make-lang.in
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cp/Make-lang.in,v
retrieving revision 1.194
diff -p -r1.194 Make-lang.in
*** cp/Make-lang.in	9 Sep 2004 22:53:51 -0000	1.194
--- cp/Make-lang.in	14 Oct 2004 23:06:07 -0000
*************** cp/except.o: cp/except.c $(CXX_TREE_H) $
*** 260,266 ****
   cp/expr.o: cp/expr.c $(CXX_TREE_H) $(TM_H) $(RTL_H) flags.h $(EXPR_H) 
toplev.h \
     except.h $(TM_P_H)
   cp/pt.o: cp/pt.c $(CXX_TREE_H) $(TM_H) cp/decl.h \
!   toplev.h $(RTL_H) except.h tree-inline.h gt-cp-pt.h
   cp/error.o: cp/error.c $(CXX_TREE_H) $(TM_H) toplev.h $(DIAGNOSTIC_H) 
\
     flags.h real.h $(LANGHOOKS_DEF_H) $(CXX_PRETTY_PRINT_H)
   cp/repo.o: cp/repo.c $(CXX_TREE_H) $(TM_H) toplev.h diagnostic.h \
--- 260,266 ----
   cp/expr.o: cp/expr.c $(CXX_TREE_H) $(TM_H) $(RTL_H) flags.h $(EXPR_H) 
toplev.h \
     except.h $(TM_P_H)
   cp/pt.o: cp/pt.c $(CXX_TREE_H) $(TM_H) cp/decl.h \
!   toplev.h $(RTL_H) except.h tree-inline.h pointer-set.h gt-cp-pt.h
   cp/error.o: cp/error.c $(CXX_TREE_H) $(TM_H) toplev.h $(DIAGNOSTIC_H) 
\
     flags.h real.h $(LANGHOOKS_DEF_H) $(CXX_PRETTY_PRINT_H)
   cp/repo.o: cp/repo.c $(CXX_TREE_H) $(TM_H) toplev.h diagnostic.h \
Index: cp/cp-tree.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cp/cp-tree.h,v
retrieving revision 1.1062
diff -p -r1.1062 cp-tree.h
*** cp/cp-tree.h	11 Oct 2004 22:49:59 -0000	1.1062
--- cp/cp-tree.h	14 Oct 2004 23:06:07 -0000
*************** extern void verify_stmt_tree
*** 4215,4221 ****
   extern tree find_tree                           (tree, tree);
   extern linkage_kind decl_linkage                (tree);
   extern tree cp_walk_subtrees (tree*, int*, walk_tree_fn,
! 				      void*, void*);
   extern int cp_cannot_inline_tree_fn (tree*);
   extern tree cp_add_pending_fn_decls (void*,tree);
   extern int cp_is_overload_p (tree);
--- 4215,4221 ----
   extern tree find_tree                           (tree, tree);
   extern linkage_kind decl_linkage                (tree);
   extern tree cp_walk_subtrees (tree*, int*, walk_tree_fn,
! 				      void*, struct pointer_set_t*);
   extern int cp_cannot_inline_tree_fn (tree*);
   extern tree cp_add_pending_fn_decls (void*,tree);
   extern int cp_is_overload_p (tree);
Index: cp/pt.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cp/pt.c,v
retrieving revision 1.935
diff -p -r1.935 pt.c
*** cp/pt.c	11 Oct 2004 22:50:00 -0000	1.935
--- cp/pt.c	14 Oct 2004 23:06:07 -0000
*************** Boston, MA 02111-1307, USA.  */
*** 32,37 ****
--- 32,38 ----
   #include "tm.h"
   #include "obstack.h"
   #include "tree.h"
+ #include "pointer-set.h"
   #include "flags.h"
   #include "cp-tree.h"
   #include "tree-inline.h"
*************** static tree convert_nontype_argument (tr
*** 113,119 ****
   static tree convert_template_argument (tree, tree, tree,
   				       tsubst_flags_t, int, tree);
   static tree get_bindings_overload (tree, tree, tree);
! static int for_each_template_parm (tree, tree_fn_t, void*, htab_t);
   static tree build_template_parm_index (int, int, int, tree, tree);
   static int inline_needs_template_parms (tree);
   static void push_inline_template_parms_recursive (tree, int);
--- 114,121 ----
   static tree convert_template_argument (tree, tree, tree,
   				       tsubst_flags_t, int, tree);
   static tree get_bindings_overload (tree, tree, tree);
! static int for_each_template_parm (tree, tree_fn_t, void*,
! 				   struct pointer_set_t*);
   static tree build_template_parm_index (int, int, int, tree, tree);
   static int inline_needs_template_parms (tree);
   static void push_inline_template_parms_recursive (tree, int);
*************** struct pair_fn_data
*** 4683,4689 ****
   {
     tree_fn_t fn;
     void *data;
!   htab_t visited;
   };

   /* Called from for_each_template_parm via walk_tree.  */
--- 4685,4691 ----
   {
     tree_fn_t fn;
     void *data;
!   struct pointer_set_t *visited;
   };

   /* Called from for_each_template_parm via walk_tree.  */
*************** for_each_template_parm_r (tree *tp, int
*** 4865,4871 ****
      considered to be the function which always returns 1.  */

   static int
! for_each_template_parm (tree t, tree_fn_t fn, void* data, htab_t 
visited)
   {
     struct pair_fn_data pfd;
     int result;
--- 4867,4874 ----
      considered to be the function which always returns 1.  */

   static int
! for_each_template_parm (tree t, tree_fn_t fn, void* data,
! 			struct pointer_set_t *visited)
   {
     struct pair_fn_data pfd;
     int result;
*************** for_each_template_parm (tree t, tree_fn_
*** 4882,4889 ****
     if (visited)
       pfd.visited = visited;
     else
!     pfd.visited = htab_create (37, htab_hash_pointer, htab_eq_pointer,
! 			       NULL);
     result = walk_tree (&t,
   		      for_each_template_parm_r,
   		      &pfd,
--- 4885,4891 ----
     if (visited)
       pfd.visited = visited;
     else
!     pfd.visited = pointer_set_create ();
     result = walk_tree (&t,
   		      for_each_template_parm_r,
   		      &pfd,
*************** for_each_template_parm (tree t, tree_fn_
*** 4891,4897 ****

     /* Clean up.  */
     if (!visited)
!     htab_delete (pfd.visited);

     return result;
   }
--- 4893,4902 ----

     /* Clean up.  */
     if (!visited)
!     {
!       pointer_set_destroy (pfd.visited);
!       pfd.visited = 0;
!     }

     return result;
   }
Index: cp/tree.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cp/tree.c,v
retrieving revision 1.416
diff -p -r1.416 tree.c
*** cp/tree.c	11 Oct 2004 15:38:23 -0000	1.416
--- cp/tree.c	14 Oct 2004 23:06:08 -0000
*************** cp_build_type_attribute_variant (tree ty
*** 1929,1935 ****

   tree
   cp_walk_subtrees (tree *tp, int *walk_subtrees_p, walk_tree_fn func,
! 		  void *data, void *htab)
   {
     enum tree_code code = TREE_CODE (*tp);
     location_t save_locus;
--- 1929,1935 ----

   tree
   cp_walk_subtrees (tree *tp, int *walk_subtrees_p, walk_tree_fn func,
! 		  void *data, struct pointer_set_t *pset)
   {
     enum tree_code code = TREE_CODE (*tp);
     location_t save_locus;
*************** cp_walk_subtrees (tree *tp, int *walk_su
*** 1938,1944 ****
   #define WALK_SUBTREE(NODE)				\
     do							\
       {							\
!       result = walk_tree (&(NODE), func, data, htab);	\
         if (result) goto out;				\
       }							\
     while (0)
--- 1938,1944 ----
   #define WALK_SUBTREE(NODE)				\
     do							\
       {							\
!       result = walk_tree (&(NODE), func, data, pset);	\
         if (result) goto out;				\
       }							\
     while (0)
Index: java/ChangeLog
===================================================================
RCS file: /cvs/gcc/gcc/gcc/java/ChangeLog,v
retrieving revision 1.1483
diff -p -r1.1483 ChangeLog
*** java/ChangeLog	13 Oct 2004 17:04:55 -0000	1.1483
--- java/ChangeLog	14 Oct 2004 23:06:09 -0000
***************
*** 1,3 ****
--- 1,8 ----
+ 2004-10-14  Matt Austern  <austern@apple.com>
+
+ 	* lang.c (java_tree_inlining_walk_subtrees): Last arg is struct
+ 	pointer_set_t* now.
+ 	
   2004-10-13  Tom Tromey  <tromey@redhat.com>

   	PR java/15578:
Index: java/lang.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/java/lang.c,v
retrieving revision 1.160
diff -p -r1.160 lang.c
*** java/lang.c	30 Sep 2004 02:16:46 -0000	1.160
--- java/lang.c	14 Oct 2004 23:06:09 -0000
*************** static void put_decl_string (const char
*** 58,64 ****
   static void put_decl_node (tree);
   static void java_print_error_function (diagnostic_context *, const 
char *);
   static tree java_tree_inlining_walk_subtrees (tree *, int *, 
walk_tree_fn,
! 					      void *, void *);
   static int merge_init_test_initialization (void * *, void *);
   static int inline_init_test_initialization (void * *, void *);
   static bool java_can_use_bit_fields_p (void);
--- 58,64 ----
   static void put_decl_node (tree);
   static void java_print_error_function (diagnostic_context *, const 
char *);
   static tree java_tree_inlining_walk_subtrees (tree *, int *, 
walk_tree_fn,
! 					      void *, struct pointer_set_t *);
   static int merge_init_test_initialization (void * *, void *);
   static int inline_init_test_initialization (void * *, void *);
   static bool java_can_use_bit_fields_p (void);
*************** java_tree_inlining_walk_subtrees (tree *
*** 706,712 ****
   				  int *subtrees ATTRIBUTE_UNUSED,
   				  walk_tree_fn func ATTRIBUTE_UNUSED,
   				  void *data ATTRIBUTE_UNUSED,
! 				  void *htab ATTRIBUTE_UNUSED)
   {
     enum tree_code code;
     tree result;
--- 706,712 ----
   				  int *subtrees ATTRIBUTE_UNUSED,
   				  walk_tree_fn func ATTRIBUTE_UNUSED,
   				  void *data ATTRIBUTE_UNUSED,
! 				  struct pointer_set_t *pset ATTRIBUTE_UNUSED)
   {
     enum tree_code code;
     tree result;
*************** java_tree_inlining_walk_subtrees (tree *
*** 714,720 ****
   #define WALK_SUBTREE(NODE)				\
     do							\
       {							\
!       result = walk_tree (&(NODE), func, data, htab);	\
         if (result)					\
   	return result;					\
       }							\
--- 714,720 ----
   #define WALK_SUBTREE(NODE)				\
     do							\
       {							\
!       result = walk_tree (&(NODE), func, data, pset);	\
         if (result)					\
   	return result;					\
       }							\

Re: [Committed] Use special-purpose hash table to speed up walk_tree

[Phil Edwards]

On Thu, Oct 14, 2004 at 04:15:44PM -0700, Matt Austern wrote:
> + /* A pointer sets is represented as a simple open-addressing hash

Grammar typo, s/sets/set/, surely?

-- 
Behind everything some further thing is found, forever; thus the tree behind
the bird, stone beneath soil, the sun behind Urth.  Behind our efforts, let
there be found our efforts.
              - Ascian saying, as related by Loyal to the Group of Seventeen

Re: [Committed] Use special-purpose hash table to speed up walk_tree

[Matt Austern]

On Oct 14, 2004, at 4:21 PM, Phil Edwards wrote:

> On Thu, Oct 14, 2004 at 04:15:44PM -0700, Matt Austern wrote:
>> + /* A pointer sets is represented as a simple open-addressing hash
>
> Grammar typo, s/sets/set/, surely?

Oops.

Re: [Committed] Use special-purpose hash table to speed up walk_tree

[Jakub Jelinek]

On Thu, Oct 14, 2004 at 04:15:44PM -0700, Matt Austern wrote:
> This patch isn't really as big as it looks.  walk_tree allows you to 
> provide a hash table to keep track of which nodes have already been 
> seen.  We were using htab_t, a general-purpose hash table with lots of 
> knobs for the client to tweak.  This patch replaces it with a 
> special-purpose hash table that has no more functionality than 
> walk_tree needs.  In particular, this special-purpose hash table 
> doesn't support deletion, doesn't give its client control over resizing 
> policy, and doesn't allow its client to specify the hash function or 
> equality function.  (It just uses the values of the pointers 
> themselves.)
> 
> Bootstrapped and tested (C, C++, Java) on powerpc-apple-darwin.  This 
> gives a 2% speedup on building QT.

But on x86-64-redhat-linux essentially makes even bootstrap impossible
(well, I have killed it after it spent more than 10 minutes compiling
insn-recog or insn-attrtab by stage1/cc1).
hash1's distribution is less than perfect.

I have gathered statistics taken from the hash table at a random time
I Ctrl-C cc1 compiling insn-recog.c.

{log_slots = 16, n_slots = 65536, n_elements = 16385, slots = 0x2a9b261010}
average chain length 7991
hash 21703 count 887
hash 21705 count 882
hash 21704 count 856
hash 21706 count 817
hash 21702 count 780
hash 21696 count 726
hash 21686 count 722
hash 21693 count 709
hash 21689 count 695
hash 21690 count 692
hash 21695 count 686
hash 21697 count 680
hash 21691 count 666
hash 21684 count 653
hash 21687 count 650
hash 21685 count 633
hash 21694 count 607
hash 21692 count 588
hash 21688 count 571
hash 21698 count 541
hash 21683 count 539
hash 21681 count 522
hash 21682 count 520
hash 21680 count 324
hash 21701 count 183
hash 21699 count 41
hash 21343 count 31
hash 21342 count 24
hash 21707 count 22
hash 21346 count 16
hash 21249 count 16
hash 21344 count 14
hash 21315 count 11
all others count 81

The hash table contains 21249 NULLs, then full slots (with a couple
of NULLs near the beginning, but only a few), and from slot 37875
onwards till the end of the hash table there are NULLs again.

Shouldn't we multiply by 2^64 / phi instead of 2^32 / phi when
long is 64-bit?

	Jakub

Re: [Committed] Use special-purpose hash table to speed up walk_tree

[Steven Bosscher]

On Saturday 16 October 2004 11:47, Jakub Jelinek wrote:
> On Thu, Oct 14, 2004 at 04:15:44PM -0700, Matt Austern wrote:
> > This patch isn't really as big as it looks.  walk_tree allows you to
> > provide a hash table to keep track of which nodes have already been
> > seen.  We were using htab_t, a general-purpose hash table with lots of
> > knobs for the client to tweak.  This patch replaces it with a
> > special-purpose hash table that has no more functionality than
> > walk_tree needs.  In particular, this special-purpose hash table
> > doesn't support deletion, doesn't give its client control over resizing
> > policy, and doesn't allow its client to specify the hash function or
> > equality function.  (It just uses the values of the pointers
> > themselves.)
> >
> > Bootstrapped and tested (C, C++, Java) on powerpc-apple-darwin.  This
> > gives a 2% speedup on building QT.
>
> But on x86-64-redhat-linux essentially makes even bootstrap impossible
> (well, I have killed it after it spent more than 10 minutes compiling
> insn-recog or insn-attrtab by stage1/cc1).
> hash1's distribution is less than perfect.

Ah, I was wondering why my bootstrap was so slow recently :-)

It would have been nice if this patch had been tested better.  Good
for you, 2% on QT, but what are the effects on other code?  And are
we in stage3 now or not?  I did not see this idea on Mark's list of
things that would be allowed in.

And why did Mark approve this offline, isn't it the policy that a
patch is posted to gcc-patches and reviewed in public?

Gr.
Steven

Re: [Committed] Use special-purpose hash table to speed up walk_tree

[Jakub Jelinek]

[-- Attachment #1: Type: text/plain, Size: 444 bytes --]

On Sat, Oct 16, 2004 at 05:47:08AM -0400, Jakub Jelinek wrote:
> But on x86-64-redhat-linux essentially makes even bootstrap impossible
> (well, I have killed it after it spent more than 10 minutes compiling
> insn-recog or insn-attrtab by stage1/cc1).
> hash1's distribution is less than perfect.

For the hash function I'm trying these patches now:

(both do the same, not sure if the first one is ok regarding absolute
portability).

	Jakub

[-- Attachment #2: P --]
[-- Type: text/plain, Size: 1235 bytes --]

2004-10-16  Jakub Jelinek  <jakub@redhat.com>

	* pointer-set.c (hash1): Use integer part of 2^64 / phi
	instead 2^32 / phi if long is 64-bit.

--- gcc/pointer-set.c.jj	2004-10-15 16:36:32.000000000 +0200
+++ gcc/pointer-set.c	2004-10-16 12:06:50.420664237 +0200
@@ -46,8 +46,8 @@ struct pointer_set_t
    relatively prime to 2^sizeof(size_t).  The result is two words.
    Discard the most significant word, and return the most significant
    N bits of the least significant word.  As suggested by Knuth, our
-   choice for A is the integer part of 2^32 / phi, where phi is the
-   golden ratio.
+   choice for A is the integer part of (ULONG_MAX + 1.0) / phi, where phi
+   is the golden ratio.
 
    We don't need to do anything special for full-width multiplication
    because we're only interested in the least significant word of the
@@ -56,7 +56,11 @@ struct pointer_set_t
 static inline size_t
 hash1 (const void *p, unsigned long max, unsigned long logmax)
 {
+#if ULONG_MAX > UINT_MAX
+  const unsigned long A = 0x9e3779b97f4a7c16ul;
+#else
   const unsigned long A = 0x9e3779b9u;
+#endif
   const unsigned long shift = sizeof(unsigned long) * CHAR_BIT - logmax;
 
   return ((A * (unsigned long) p) >> shift) & (max - 1);

[-- Attachment #3: P2 --]
[-- Type: text/plain, Size: 1428 bytes --]

2004-10-16  Jakub Jelinek  <jakub@redhat.com>

	* pointer-set.c (hash1): Use integer part of 2^64 / phi
	instead 2^32 / phi if long is 64-bit.

--- gcc/pointer-set.c.jj	2004-10-15 16:36:32.000000000 +0200
+++ gcc/pointer-set.c	2004-10-16 12:23:49.722200909 +0200
@@ -46,8 +46,8 @@ struct pointer_set_t
    relatively prime to 2^sizeof(size_t).  The result is two words.
    Discard the most significant word, and return the most significant
    N bits of the least significant word.  As suggested by Knuth, our
-   choice for A is the integer part of 2^32 / phi, where phi is the
-   golden ratio.
+   choice for A is the integer part of (ULONG_MAX + 1.0) / phi, where phi
+   is the golden ratio.
 
    We don't need to do anything special for full-width multiplication
    because we're only interested in the least significant word of the
@@ -57,9 +57,14 @@ static inline size_t
 hash1 (const void *p, unsigned long max, unsigned long logmax)
 {
   const unsigned long A = 0x9e3779b9u;
-  const unsigned long shift = sizeof(unsigned long) * CHAR_BIT - logmax;
+  unsigned long B;
+  const unsigned long shift = sizeof (unsigned long) * CHAR_BIT - logmax;
 
-  return ((A * (unsigned long) p) >> shift) & (max - 1);
+  if (sizeof (unsigned long) * CHAR_BIT > 32)
+    B = ((A << 16) << 16) | 0x7f4a7c16u;
+  else
+    B = A;
+  return ((B * (unsigned long) p) >> shift) & (max - 1);
 }
 
 /* Allocate an empty pointer set. */

Re: [Committed] Use special-purpose hash table to speed up walk_tree

[Jakub Jelinek]

On Sat, Oct 16, 2004 at 06:37:12AM -0400, Jakub Jelinek wrote:
> On Sat, Oct 16, 2004 at 05:47:08AM -0400, Jakub Jelinek wrote:
> > But on x86-64-redhat-linux essentially makes even bootstrap impossible
> > (well, I have killed it after it spent more than 10 minutes compiling
> > insn-recog or insn-attrtab by stage1/cc1).
> > hash1's distribution is less than perfect.
> 
> For the hash function I'm trying these patches now:
> 
> (both do the same, not sure if the first one is ok regarding absolute
> portability).

With either of these patches the average chain length on the same
table (16384 pointers, 65536 slots) is 1.1, there is one occurence of 4 pointers
hashed into the same slot and 44 times 3 pointers hashed into the same
slot, but never more.

Ok to commit?  Is the #if ULONG_MAX > UINT_MAX ok, or should I commit the
one without #ifs?

	Jakub

Re: [Committed] Use special-purpose hash table to speed up walk_tree

[Matt Austern]

On Oct 16, 2004, at 2:47 AM, Jakub Jelinek wrote:

> The hash table contains 21249 NULLs, then full slots (with a couple
> of NULLs near the beginning, but only a few), and from slot 37875
> onwards till the end of the hash table there are NULLs again.
>
> Shouldn't we multiply by 2^64 / phi instead of 2^32 / phi when
> long is 64-bit?

Oops, you're right.  Sorry; I didn't test on a 64-bit platform.

			--Matt

Re: [Committed] Use special-purpose hash table to speed up walk_tree

[Matt Austern]

On Oct 16, 2004, at 3:37 AM, Jakub Jelinek wrote:

> On Sat, Oct 16, 2004 at 05:47:08AM -0400, Jakub Jelinek wrote:
>> But on x86-64-redhat-linux essentially makes even bootstrap impossible
>> (well, I have killed it after it spent more than 10 minutes compiling
>> insn-recog or insn-attrtab by stage1/cc1).
>> hash1's distribution is less than perfect.
>
> For the hash function I'm trying these patches now:
>
> (both do the same, not sure if the first one is ok regarding absolute
> portability).

If it were me I'd probably use the first patch, to make absolutely sure 
we're
doing nothing but multiplication by a compile-time constant.  Probably 
the
optimizer is smart enough to optimize all away the extra stuff in the 
second
version of the patch, but I'd rather not count on that in code that 
really is
time critical.

			--Matt

Re: [Committed] Use special-purpose hash table to speed up walk_tree

[Richard Henderson]

On Sat, Oct 16, 2004 at 06:37:12AM -0400, Jakub Jelinek wrote:
> +   choice for A is the integer part of (ULONG_MAX + 1.0) / phi, where phi
> +   is the golden ratio.

Any reason not to use the computation actually described here?

Otherwise, the ifdef one's fine if you use HOST_BITS_PER_LONG
to choose one of the alternatives exactly:

#if HOST_BITS_PER_LONG == 32
  const unsigned long A = 0x9e3779b9u;
#elif HOST_BITS_PER_LONG == 64
  const unsigned long A = 0x9e3779b97f4a7c16ul;
#endif

Which will handily not compile if we ever find something else.


r~

Re: [Committed] Use special-purpose hash table to speed up walk_tree

[Jakub Jelinek]

On Sat, Oct 16, 2004 at 11:29:52AM -0700, Richard Henderson wrote:
> On Sat, Oct 16, 2004 at 06:37:12AM -0400, Jakub Jelinek wrote:
> > +   choice for A is the integer part of (ULONG_MAX + 1.0) / phi, where phi
> > +   is the golden ratio.
> 
> Any reason not to use the computation actually described here?

You mean doing the computation in FPU?

> Otherwise, the ifdef one's fine if you use HOST_BITS_PER_LONG
> to choose one of the alternatives exactly:
> 
> #if HOST_BITS_PER_LONG == 32
>   const unsigned long A = 0x9e3779b9u;
> #elif HOST_BITS_PER_LONG == 64
>   const unsigned long A = 0x9e3779b97f4a7c16ul;
> #endif
> 
> Which will handily not compile if we ever find something else.

Yeah, that looks better.

	Jakub

Re: [Committed] Use special-purpose hash table to speed up walk_tree

[Richard Henderson]

On Sat, Oct 16, 2004 at 02:34:24PM -0400, Jakub Jelinek wrote:
> You mean doing the computation in FPU?

Well, it's all constants, so why wouldn't it be folded at compile time?


r~

Re: [Committed] Use special-purpose hash table to speed up walk_tree

[Jakub Jelinek]

On Sat, Oct 16, 2004 at 11:37:41AM -0700, Richard Henderson wrote:
> On Sat, Oct 16, 2004 at 02:34:24PM -0400, Jakub Jelinek wrote:
> > You mean doing the computation in FPU?
> 
> Well, it's all constants, so why wouldn't it be folded at compile time?

Because not all hosts have long double that has big enough mantissa
to compute the exact result (nor I think we can portably use math *l
functions)?

Perhaps we can do it as a fallback:

#if HOST_BITS_PER_LONG == 32
  const unsigned long A = 0x9e3779b9u;
#elif HOST_BITS_PER_LONG == 64
  const unsigned long A = 0x9e3779b97f4a7c16ul;
#else
  const double M = (ULONG_MAX + 1.0);
  const double B = M / ((sqrt (5) - 1) / 2.0);
  const unsigned long A = B - (floor (B / M) * M);
#endif

The last one results in const unsigned long A = 0x9e3779b97f4a7000;
on x86-64, while if done with long double it gives correct
const unsigned long A = 0x9e3779b97f4a7c16; result.

	Jakub

Re: [Committed] Use special-purpose hash table to speed up walk_tree

[Richard Henderson]

On Sat, Oct 16, 2004 at 02:51:16PM -0400, Jakub Jelinek wrote:
> Because not all hosts have long double that has big enough mantissa
> to compute the exact result (nor I think we can portably use math *l
> functions)?

Ah yeah.  Well, nevermind.


r~

Re: [Committed] Use special-purpose hash table to speed up walk_tree

[Mark Mitchell]

Steven Bosscher wrote:
> On Saturday 16 October 2004 11:47, Jakub Jelinek wrote:
> 
>>But on x86-64-redhat-linux essentially makes even bootstrap impossible
>>(well, I have killed it after it spent more than 10 minutes compiling
>>insn-recog or insn-attrtab by stage1/cc1).
>>hash1's distribution is less than perfect.

In that case, go ahed and revert the patch.  I know that we normally 
require a 48-hour period, but I know Matt, and I am confident that he 
will not complain.

Then, Matt will work out how to fix it.

> It would have been nice if this patch had been tested better.  Good
> for you, 2% on QT, but what are the effects on other code?  And are
> we in stage3 now or not?  I did not see this idea on Mark's list of
> things that would be allowed in.

There is an item for improving compile-time performance; this falls 
under that.

> And why did Mark approve this offline, isn't it the policy that a
> patch is posted to gcc-patches and reviewed in public?

I don't think there is any such policy one way or the other.  Certainly, 
there is precedent for patches being approved offline.  Matt sent me the 
patch, and it looked good to me.  I didn't see any reason to test it on 
other architectures.

-- 
Mark Mitchell
CodeSourcery, LLC
mark@codesourcery.com

Re: [Committed] Use special-purpose hash table to speed up walk_tree

[Steven Bosscher]

On Sunday 17 October 2004 07:51, Mark Mitchell wrote:
> I don't think there is any such policy one way or the other.  Certainly,
> there is precedent for patches being approved offline.

I know there is, and I think it's wrong.  More eyes see more
things.


>  Matt sent me the
> patch, and it looked good to me.  I didn't see any reason to test it on
> other architectures.

Well, we've have some pretty serious breakage a few times in the
past few weeks.  Already three times the cause of this breakage
was that some patch wasn't tested on some architecture.  So I
see lots of reasons to require better testing for patches when
the mainlne is in stage3.

Can we make it a requirement that larger patches like this should
be tested on three platforms when the mainline is in stage3?

Gr.
Steven


Index: develop.html
===================================================================
RCS file: /cvs/gcc/wwwdocs/htdocs/develop.html,v
retrieving revision 1.52
diff -c -3 -p -r1.52 develop.html
*** develop.html	11 Sep 2004 14:55:46 -0000	1.52
--- develop.html	17 Oct 2004 09:53:45 -0000
*************** back-end.</p>
*** 123,140 ****
  <p>During this period, the only (non-documentation) changes that may be
  made are changes that fix bugs or new ports which do not require changes
  to other parts of the compiler.
! New functionality may not be introduced during this period.</p>
  
  <p><strong>Rationale</strong></p>
  
  <p>In order to produce releases on a regular schedule, we must ensure
  that the mainline is reasonably stable some time before we make the
! release.  Therefore, more radical changes must be made earlier in the
! cycle, so that we have time to fix any problems that result.</p>
  
  <p>In order to reach higher standards of quality, we must focus on
! fixing bugs; by working exclusively on bug-fixing through Stage 3, we
! will have a higher quality source base as we prepare for a release.</p>
  
  <p>Although maintaining a development branch, including merging new
  changes from the mainline, is somewhat burdensome, the absolute worst
--- 123,147 ----
  <p>During this period, the only (non-documentation) changes that may be
  made are changes that fix bugs or new ports which do not require changes
  to other parts of the compiler.
! 
! In principle, new functionality may not be introduced during this period.
! However, the release manager may still allow patches in that add new
! functionality.  Such patches should be validated on three different
! targets, each targeting a different microprocessor family, before the
! patch can be commited.</p>
  
  <p><strong>Rationale</strong></p>
  
  <p>In order to produce releases on a regular schedule, we must ensure
  that the mainline is reasonably stable some time before we make the
! release.  Therefore, more radical changes must either be made earlier
! in the cycle, so that we have time to fix any problems that result, or
! very thoroughly tested, to reduce the risk of destabilizing the mainline
! as much as possible.</p>
  
  <p>In order to reach higher standards of quality, we must focus on
! fixing bugs; by working almost exclusively on bug-fixing through Stage 3,
! we will have a higher quality source base as we prepare for a release.</p>
  
  <p>Although maintaining a development branch, including merging new
  changes from the mainline, is somewhat burdensome, the absolute worst

Re: [Committed] Use special-purpose hash table to speed up walk_tree

[Matt Austern]

On Oct 17, 2004, at 2:58 AM, Steven Bosscher wrote:

> On Sunday 17 October 2004 07:51, Mark Mitchell wrote:
>> I don't think there is any such policy one way or the other.  
>> Certainly,
>> there is precedent for patches being approved offline.
>
> I know there is, and I think it's wrong.  More eyes see more
> things.
>
>
>>  Matt sent me the
>> patch, and it looked good to me.  I didn't see any reason to test it 
>> on
>> other architectures.
>
> Well, we've have some pretty serious breakage a few times in the
> past few weeks.  Already three times the cause of this breakage
> was that some patch wasn't tested on some architecture.  So I
> see lots of reasons to require better testing for patches when
> the mainlne is in stage3.
>
> Can we make it a requirement that larger patches like this should
> be tested on three platforms when the mainline is in stage3?

That may be a good idea, but bear in mind that it probably would
not have caught this problem.  I don't regularly use a platform
where pointers are 64-bit, so if I were testing this on three
platforms it probably would have been three 32-bit platforms.
If we're looking for diversity, it had probably better be
something like this: at least one non-Linux platform, at least
one non-ELF platform, at least one non-x86 platform, at least
two different word sizes.

			--Matt 

Re: [Committed] Use special-purpose hash table to speed up walk_tree

[Mark Mitchell]

Steven Bosscher wrote:

>On Sunday 17 October 2004 07:51, Mark Mitchell wrote:
>  
>
>>I don't think there is any such policy one way or the other.  Certainly,
>>there is precedent for patches being approved offline.
>>    
>>
>
>I know there is, and I think it's wrong.  More eyes see more
>things.
>  
>
Yes, but I do have the authority to approve patches.  If we had a 
no-offline-approval policy, what would have happenned is that Matt would 
have posted the patch, and I would have immediately approved it.  That's 
no different that me approving the patch offline; we would still have 
had a broken patch committed to the tree.

To make things more substantive, we could require that all patches be 
posted for a period of time (24 hrs?) before being approved.  That seems 
silly though; some patches are very obvious.  So, we'd have to make 
judgement calls about what's appropriate in what situations.  If I'd 
anticipated problems, I would have just asked for further testing in the 
first place.

In short, I don't see that there's a policy problem.  If there's a 
problem, it's just that I didn't anticipate the 64-bit mode issues, but, 
hey, we all make mistakes.

>Can we make it a requirement that larger patches like this should
>be tested on three platforms when the mainline is in stage3?
>  
>
I don't think this is a large patch.  I actually thought it was pretty 
straightforward.  It did have a bug, but that happens sometime.  I don't 
think that requiring testing on three platforms for this kind of patch 
would be profitable, overall.

-- 
Mark Mitchell
CodeSourcery, LLC
(916) 791-8304
mark@codesourcery.com

Re: [Committed] Use special-purpose hash table to speed up walk_tree

[Gerald Pfeifer]

On Sun, 17 Oct 2004, Steven Bosscher wrote:
> Index: develop.html
> ===================================================================
>  <p>In order to reach higher standards of quality, we must focus on
> ! fixing bugs; by working almost exclusively on bug-fixing through Stage 3,
> ! we will have a higher quality source base as we prepare for a release.</p>

This part is okay; I don't think the other two hunks are sufficiently
undisputed, though.

Gerald

Re: [Committed] Use special-purpose hash table to speed up walk_tree

[Richard Kenner]

    Yes, but I do have the authority to approve patches.  If we had a 
    no-offline-approval policy, what would have happenned is that Matt would 
    have posted the patch, and I would have immediately approved it.  That's 
    no different that me approving the patch offline; we would still have 
    had a broken patch committed to the tree.

I agree.  The purpose of posting patches to gcc-patches is indeed to have
many sets of eyes look at it, but many of those are after the patch is
checked in.  That's the case whether the patch is one written by somebody
with global write privs, approved on-list, or approved off-list.