[PATCH] Avoid recursive use of hash tables in varasm.c

[Jakub Jelinek <jakub at redhat dot com>]

On Thu, May 12, 2005 at 11:08:19AM -0400, Vladimir Makarov wrote:
> >I see 2 possible solutions for this:
> >
> >One is add a hashval_t element into the constant_descriptor_tree structure,
> >use htab_find{,_slot}_with_hash after calling const_hash_1 () explicitely
> >instead of htab_find{,_slot} and just return the recorded hashval_t from
> >const_desc_hash.  This means the hash table will never be used recursively,
> >the drawback is bigger memory footprint (4 bytes per entry on 32-bit
> >and 8 bytes per entry on 64-bit hosts).
> > 
> >
> I'd prefer the first solution even if it is more expensive (although 
> these data are not so big to worry about smaller footprint).

Here is the patch that does that (and on gcc-3_4-branch fixes the
miscompilation).  Ok for HEAD/4.0, maybe 3.4 as well?

2005-05-16  Jakub Jelinek  <jakub@redhat.com>

	* varasm.c (struct constant_descriptor_tree): Add hash field.
	(const_desc_hash): Just return hash field.
	(const_desc_eq): If hash values are different, return 0 immediately.
	(output_constant_def): Compute hash field of temporary key, use
	htab_find_slot_with_hash instead of htab_find_slot.  Set hash in
	newly built constant descriptor.
	(lookup_constant_def): Compute hash field of temporary key, use
	htab_find_with_hash instead of htab_find.

--- gcc/varasm.c.jj	2005-05-16 09:44:33.000000000 +0200
+++ gcc/varasm.c	2005-05-16 15:38:36.000000000 +0200
@@ -2366,6 +2366,11 @@ struct constant_descriptor_tree GTY(())
 
   /* The value of the constant.  */
   tree value;
+
+  /* Hash of value.  Computing the hash from value each time
+     hashfn is called can't work properly, as that means recursive
+     use of the hash table during hash table expansion.  */
+  hashval_t hash;
 };
 
 static GTY((param_is (struct constant_descriptor_tree)))
@@ -2379,7 +2384,7 @@ static void maybe_output_constant_def_co
 static hashval_t
 const_desc_hash (const void *ptr)
 {
-  return const_hash_1 (((struct constant_descriptor_tree *)ptr)->value);
+  return ((struct constant_descriptor_tree *)ptr)->hash;
 }
 
 static hashval_t
@@ -2479,8 +2484,11 @@ const_hash_1 (const tree exp)
 static int
 const_desc_eq (const void *p1, const void *p2)
 {
-  return compare_constant (((struct constant_descriptor_tree *)p1)->value,
-			   ((struct constant_descriptor_tree *)p2)->value);
+  const struct constant_descriptor_tree *c1 = p1;
+  const struct constant_descriptor_tree *c2 = p2;
+  if (c1->hash != c2->hash)
+    return 0;
+  return compare_constant (c1->value, c2->value);
 }
 
 /* Compare t1 and t2, and return 1 only if they are known to result in
@@ -2750,12 +2758,14 @@ output_constant_def (tree exp, int defer
   /* Look up EXP in the table of constant descriptors.  If we didn't find
      it, create a new one.  */
   key.value = exp;
-  loc = htab_find_slot (const_desc_htab, &key, INSERT);
+  key.hash = const_hash_1 (exp);
+  loc = htab_find_slot_with_hash (const_desc_htab, &key, key.hash, INSERT);
 
   desc = *loc;
   if (desc == 0)
     {
       desc = build_constant_desc (exp);
+      desc->hash = key.hash;
       *loc = desc;
     }
 
@@ -2858,7 +2868,8 @@ lookup_constant_def (tree exp)
   struct constant_descriptor_tree key;
 
   key.value = exp;
-  desc = htab_find (const_desc_htab, &key);
+  key.hash = const_hash_1 (exp);
+  desc = htab_find_with_hash (const_desc_htab, &key, key.hash);
 
   return (desc ? desc->rtl : NULL_RTX);
 }

	Jakub