This is the mail archive of the mailing list for the GCC project.

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[PATCH] Allow (limited) recursive use of hash tables

contains a testcase that with current gcc-3_4-branch as well as
Red Hat 3.4.3 and 3.4.2 based compilers exhibits an interesting
const_desc_htab hash table's hash function calls const_hash_1,
which in turn can call decode_addr_const (for ADDR_EXPR/FDESC_EXPR)
and that can call output_constant_def (on the above referenced
testcase there is <ADDR_EXPR <CONSTRUCTOR ...>> in the const_desc_htab
table's value) and that in turn calls htab_find_slot (const_desc_htab, ...).
This is problematic in hash table expansion.
Current htab_expand puts the new elements array as htab->elements
and afterwards iterates over the old elements array and inserts
the entries into initially empty hash table.  For each of the entries
it calls htab->hash_f.  Now as const_desc_htab->hash_f uses
const_desc_htab hashtable internally, it can happen that
what it is looking up is not yet in the new hash table (and the old
elements array is not accessible), so it creates new SYMBOL_REF
(but deferred one, so it is never output and results in undefined
references to .LC* symbols).

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).

Alternatively, htab_expand can be changed to allow limited recursion.
Particularly, the hash table can be used read-only from hash_f function
(where read-only means no entry insertion or deletion, statistics can
be changed).  That's all that varasm.c actually needs (the hash function
has been already called on the entry before, so it will never need to
add new things into the hash table).

I have implemented the latter.

The static int recursive variable is in there because we should IMHO
allow htab_find_slot with INSERT called from htab_f, as long as it doesn't
actually insert new entry.  But as soon as htab is filled to 3/4,
each such htab_find_slot would try to call htab_expand again.

2005-05-11  Jakub Jelinek  <>

	* hashtab.c (htab_expand): Allow limited use of the hash table
	in hash_f function.

--- libiberty/hashtab.c.jj	2004-05-22 18:12:36.000000000 +0200
+++ libiberty/hashtab.c	2005-05-11 16:32:14.000000000 +0200
@@ -514,14 +514,24 @@ htab_expand (htab)
   PTR *p;
   PTR *nentries;
   size_t nsize, osize, elts;
+  size_t onelements, ondeleted;
+  struct htab nhtab;
+  static int recursive;
   unsigned int oindex, nindex;
   oentries = htab->entries;
   oindex = htab->size_prime_index;
   osize = htab->size;
   olimit = oentries + osize;
+  onelements = htab->n_elements;
+  ondeleted = htab->n_deleted;
   elts = htab_elements (htab);
+  if (recursive)
+    return htab->n_elements < htab->size;
+  recursive = 1;
   /* Resize only when table after removal of unused elements is either
      too full or too empty.  */
   if (elts * 2 > osize || (elts * 8 < osize && osize > 32))
@@ -541,12 +551,13 @@ htab_expand (htab)
     nentries = (PTR *) (*htab->alloc_f) (nsize, sizeof (PTR *));
   if (nentries == NULL)
-    return 0;
-  htab->entries = nentries;
-  htab->size = nsize;
-  htab->size_prime_index = nindex;
-  htab->n_elements -= htab->n_deleted;
-  htab->n_deleted = 0;
+    {
+      recursive = 0;
+      return 0;
+    }
+  nhtab.entries = nentries;
+  nhtab.size = nsize;
+  nhtab.size_prime_index = nindex;
   p = oentries;
@@ -555,7 +566,7 @@ htab_expand (htab)
       if (x != EMPTY_ENTRY && x != DELETED_ENTRY)
-	  PTR *q = find_empty_slot_for_expand (htab, (*htab->hash_f) (x));
+	  PTR *q = find_empty_slot_for_expand (&nhtab, (*htab->hash_f) (x));
 	  *q = x;
@@ -564,6 +575,23 @@ htab_expand (htab)
   while (p < olimit);
+  /* Only modify *htab once nentries array is prepared, so that
+     htab->hash_f can use the hash table recursively (as long as
+     it never inserts new entries).  */
+  htab->entries = nentries;
+  htab->size = nsize;
+  htab->size_prime_index = nindex;
+  /* Quick check that nobody inserted new elements into the oentries
+     array nor removed any.  */
+  if (htab->n_elements != onelements || htab->n_deleted != ondeleted)
+    abort ();
+  htab->n_elements -= htab->n_deleted;
+  htab->n_deleted = 0;
+  recursive = 0;
   if (htab->free_f != NULL)
     (*htab->free_f) (oentries);
   else if (htab->free_with_arg_f != NULL)


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]