allow storing values directly in hash tables

gcc/

	* hash-table.h: Add a template arg to choose between storing values
	and storing pointers to values, and then provide partial
	specializations for both.
	* tree-browser.c (tree_upper_hasher): Provide the type the hash table
	should store, not the type values should point to.
	* tree-into-ssa.c (var_info_hasher): Likewise.
	* tree-ssa-dom.c (expr_elt_hasher): Likewise.
	* tree-complex.c: Adjust.
	* tree-hasher.h (int_tree_hasher): store int_tree_map in the hash
	table instead of int_tree_map *.
	* tree-parloops.c: Adjust.
	* tree-ssa-reassoc.c (ocount_hasher): Don't lie to hash_map about what
	type is being stored.
	* tree-vectorizer.c: Adjust.

From-SVN: r211937

10 files changed, 800 insertions, 121 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index ca591a6..bf1a716 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,5 +1,22 @@
 2014-06-24  Trevor Saunders  <tsaunders@mozilla.com>
 
+	* hash-table.h: Add a template arg to choose between storing values
+	and storing pointers to values, and then provide partial
+	specializations for both.
+	* tree-browser.c (tree_upper_hasher): Provide the type the hash table
+	should store, not the type values should point to.
+	* tree-into-ssa.c (var_info_hasher): Likewise.
+	* tree-ssa-dom.c (expr_elt_hasher): Likewise.
+	* tree-complex.c: Adjust.
+	* tree-hasher.h (int_tree_hasher): store int_tree_map in the hash
+	table instead of int_tree_map *.
+	* tree-parloops.c: Adjust.
+	* tree-ssa-reassoc.c (ocount_hasher): Don't lie to hash_map about what
+	type is being stored.
+	* tree-vectorizer.c: Adjust.
+
+2014-06-24  Trevor Saunders  <tsaunders@mozilla.com>
+
 	* hash-table.h: Remove a layer of indirection from hash_table so that
 	it contains the hash table's data instead of a pointer to the data.
 	* alloc-pool.c, asan.c, attribs.c, bitmap.c, cfg.c,
diff --git a/gcc/hash-table.h b/gcc/hash-table.h
index 41cc19e..22af12f 100644
--- a/gcc/hash-table.h
+++ b/gcc/hash-table.h
@@ -272,19 +272,18 @@ typed_noop_remove <Type>::remove (Type *p ATTRIBUTE_UNUSED)
 template <typename Type>
 struct pointer_hash : typed_noop_remove <Type>
 {
-  typedef Type value_type;
-  typedef Type compare_type;
+  typedef Type *value_type;
+  typedef Type *compare_type;
+  typedef int store_values_directly;
 
-  static inline hashval_t
-  hash (const value_type *);
+  static inline hashval_t hash (const value_type &);
 
-  static inline int
-  equal (const value_type *existing, const compare_type *candidate);
+  static inline bool equal (const value_type &existing, const compare_type &candidate);
 };
 
 template <typename Type>
 inline hashval_t
-pointer_hash <Type>::hash (const value_type *candidate)
+pointer_hash <Type>::hash (const value_type &candidate)
 {
   /* This is a really poor hash function, but it is what the current code uses,
      so I am reusing it to avoid an additional axis in testing.  */
@@ -292,9 +291,9 @@ pointer_hash <Type>::hash (const value_type *candidate)
 }
 
 template <typename Type>
-inline int
-pointer_hash <Type>::equal (const value_type *existing,
-			   const compare_type *candidate)
+inline bool
+pointer_hash <Type>::equal (const value_type &existing,
+			   const compare_type &candidate)
 {
   return existing == candidate;
 }
@@ -319,10 +318,147 @@ extern unsigned int hash_table_higher_prime_index (unsigned long n);
 extern hashval_t hash_table_mod1 (hashval_t hash, unsigned int index);
 extern hashval_t hash_table_mod2 (hashval_t hash, unsigned int index);
 
+/* The below is some template meta programming to decide if we should use the
+   hash table partial specialization that directly stores value_type instead of
+   pointers to value_type.  If the Descriptor type defines the type
+   Descriptor::store_values_directly then values are stored directly otherwise
+   pointers to them are stored.  */
+template<typename T> struct notype { typedef void type; };
+
+template<typename T, typename = void>
+struct storage_tester
+{
+  static const bool value = false;
+};
+
+template<typename T>
+struct storage_tester<T, typename notype<typename
+					 T::store_values_directly>::type>
+{
+  static const bool value = true;
+};
+
+ template<typename Traits>
+ struct has_is_deleted
+{
+  template<typename U, bool (*)(U &)> struct helper {};
+  template<typename U> static char test (helper<U, U::is_deleted> *);
+  template<typename U> static int test (...);
+  static const bool value = sizeof (test<Traits> (0)) == sizeof (char);
+};
+
+template<typename Type, typename Traits, bool = has_is_deleted<Traits>::value>
+struct is_deleted_helper
+{
+  static inline bool
+  call (Type &v)
+  {
+    return Traits::is_deleted (v);
+  }
+};
+
+template<typename Type, typename Traits>
+struct is_deleted_helper<Type *, Traits, false>
+{
+  static inline bool
+  call (Type *v)
+  {
+    return v == HTAB_DELETED_ENTRY;
+  }
+};
+
+ template<typename Traits>
+ struct has_is_empty
+{
+  template<typename U, bool (*)(U &)> struct helper {};
+  template<typename U> static char test (helper<U, U::is_empty> *);
+  template<typename U> static int test (...);
+  static const bool value = sizeof (test<Traits> (0)) == sizeof (char);
+};
+
+template<typename Type, typename Traits, bool = has_is_deleted<Traits>::value>
+struct is_empty_helper
+{
+  static inline bool
+  call (Type &v)
+  {
+    return Traits::is_empty (v);
+  }
+};
+
+template<typename Type, typename Traits>
+struct is_empty_helper<Type *, Traits, false>
+{
+  static inline bool
+  call (Type *v)
+  {
+    return v == HTAB_EMPTY_ENTRY;
+  }
+};
+
+ template<typename Traits>
+ struct has_mark_deleted
+{
+  template<typename U, void (*)(U &)> struct helper {};
+  template<typename U> static char test (helper<U, U::mark_deleted> *);
+  template<typename U> static int test (...);
+  static const bool value = sizeof (test<Traits> (0)) == sizeof (char);
+};
+
+template<typename Type, typename Traits, bool = has_is_deleted<Traits>::value>
+struct mark_deleted_helper
+{
+  static inline void
+  call (Type &v)
+  {
+    Traits::mark_deleted (v);
+  }
+};
+
+template<typename Type, typename Traits>
+struct mark_deleted_helper<Type *, Traits, false>
+{
+  static inline void
+  call (Type *&v)
+  {
+    v = static_cast<Type *> (HTAB_DELETED_ENTRY);
+  }
+};
+
+ template<typename Traits>
+ struct has_mark_empty
+{
+  template<typename U, void (*)(U &)> struct helper {};
+  template<typename U> static char test (helper<U, U::mark_empty> *);
+  template<typename U> static int test (...);
+  static const bool value = sizeof (test<Traits> (0)) == sizeof (char);
+};
+
+template<typename Type, typename Traits, bool = has_is_deleted<Traits>::value>
+struct mark_empty_helper
+{
+  static inline void
+  call (Type &v)
+  {
+    Traits::mark_empty (v);
+  }
+};
+
+template<typename Type, typename Traits>
+struct mark_empty_helper<Type *, Traits, false>
+{
+  static inline void
+  call (Type *&v)
+  {
+    v = static_cast<Type *> (HTAB_EMPTY_ENTRY);
+  }
+};
 
 /* User-facing hash table type.
 
-   The table stores elements of type Descriptor::value_type.
+   The table stores elements of type Descriptor::value_type, or pointers to
+   objects of type value_type if the descriptor does not define the type
+   store_values_directly.
 
    It hashes values with the hash member function.
      The table currently works with relatively weak hash functions.
@@ -340,11 +476,21 @@ extern hashval_t hash_table_mod2 (hashval_t hash, unsigned int index);
    Specify the template Allocator to allocate and free memory.
      The default is xcallocator.
 
+     Storage is an implementation detail and should not be used outside the
+     hash table code.
+
 */
 template <typename Descriptor,
-	 template<typename Type> class Allocator= xcallocator>
+	 template<typename Type> class Allocator= xcallocator,
+	 bool Storage = storage_tester<Descriptor>::value>
 class hash_table
 {
+};
+
+template <typename Descriptor,
+	 template<typename Type> class Allocator>
+class hash_table<Descriptor, Allocator, false>
+{
   typedef typename Descriptor::value_type value_type;
   typedef typename Descriptor::compare_type compare_type;
 
@@ -428,7 +574,7 @@ public:
     iterator (value_type **slot, value_type **limit) :
       m_slot (slot), m_limit (limit) {}
 
-    inline value_type &operator * () { return **m_slot; }
+    inline value_type *operator * () { return *m_slot; }
     void slide ();
     inline iterator &operator ++ ();
     bool operator != (const iterator &other) const
@@ -485,7 +631,7 @@ private:
 };
 
 template<typename Descriptor, template<typename Type> class Allocator>
-hash_table<Descriptor, Allocator>::hash_table (size_t size) :
+hash_table<Descriptor, Allocator, false>::hash_table (size_t size) :
   m_n_elements (0), m_n_deleted (0), m_searches (0), m_collisions (0)
 {
   unsigned int size_prime_index;
@@ -500,7 +646,7 @@ hash_table<Descriptor, Allocator>::hash_table (size_t size) :
 }
 
 template<typename Descriptor, template<typename Type> class Allocator>
-hash_table<Descriptor, Allocator>::~hash_table ()
+hash_table<Descriptor, Allocator, false>::~hash_table ()
 {
   for (size_t i = m_size - 1; i < m_size; i--)
     if (m_entries[i] != HTAB_EMPTY_ENTRY && m_entries[i] != HTAB_DELETED_ENTRY)
@@ -518,7 +664,8 @@ hash_table<Descriptor, Allocator>::~hash_table ()
 
 template<typename Descriptor, template<typename Type> class Allocator>
 typename Descriptor::value_type **
-hash_table<Descriptor, Allocator>::find_empty_slot_for_expand (hashval_t hash)
+hash_table<Descriptor, Allocator, false>
+::find_empty_slot_for_expand (hashval_t hash)
 {
   hashval_t index = hash_table_mod1 (hash, m_size_prime_index);
   size_t size = m_size;
@@ -554,7 +701,7 @@ hash_table<Descriptor, Allocator>::find_empty_slot_for_expand (hashval_t hash)
 
 	  template<typename Descriptor, template<typename Type> class Allocator>
 void
-hash_table<Descriptor, Allocator>::expand ()
+hash_table<Descriptor, Allocator, false>::expand ()
 {
   value_type **oentries = m_entries;
   unsigned int oindex = m_size_prime_index;
@@ -606,7 +753,7 @@ hash_table<Descriptor, Allocator>::expand ()
 
 template<typename Descriptor, template<typename Type> class Allocator>
 void
-hash_table<Descriptor, Allocator>::empty ()
+hash_table<Descriptor, Allocator, false>::empty ()
 {
   size_t size = m_size;
   value_type **entries = m_entries;
@@ -639,7 +786,7 @@ hash_table<Descriptor, Allocator>::empty ()
 
 template<typename Descriptor, template<typename Type> class Allocator>
 void
-hash_table<Descriptor, Allocator>::clear_slot (value_type **slot)
+hash_table<Descriptor, Allocator, false>::clear_slot (value_type **slot)
 {
   if (slot < m_entries || slot >= m_entries + size ()
       || *slot == HTAB_EMPTY_ENTRY || *slot == HTAB_DELETED_ENTRY)
@@ -657,7 +804,7 @@ hash_table<Descriptor, Allocator>::clear_slot (value_type **slot)
 
 template<typename Descriptor, template<typename Type> class Allocator>
 typename Descriptor::value_type *
-hash_table<Descriptor, Allocator>
+hash_table<Descriptor, Allocator, false>
 ::find_with_hash (const compare_type *comparable, hashval_t hash)
 {
   m_searches++;
@@ -695,7 +842,7 @@ hash_table<Descriptor, Allocator>
 
 template<typename Descriptor, template<typename Type> class Allocator>
 typename Descriptor::value_type **
-hash_table<Descriptor, Allocator>
+hash_table<Descriptor, Allocator, false>
 ::find_slot_with_hash (const compare_type *comparable, hashval_t hash,
 		       enum insert_option insert)
 {
@@ -756,7 +903,7 @@ hash_table<Descriptor, Allocator>
 
 template<typename Descriptor, template<typename Type> class Allocator>
 void
-hash_table<Descriptor, Allocator>
+hash_table<Descriptor, Allocator, false>
 ::remove_elt_with_hash (const compare_type *comparable, hashval_t hash)
 {
   value_type **slot = find_slot_with_hash (comparable, hash, NO_INSERT);
@@ -773,12 +920,11 @@ hash_table<Descriptor, Allocator>
    each live entry.  If CALLBACK returns false, the iteration stops.
    ARGUMENT is passed as CALLBACK's second argument. */
 
-template<typename Descriptor,
-	  template<typename Type> class Allocator>
+template<typename Descriptor, template<typename Type> class Allocator>
 template<typename Argument,
 	  int (*Callback) (typename Descriptor::value_type **slot, Argument argument)>
 void
-hash_table<Descriptor, Allocator>::traverse_noresize (Argument argument)
+hash_table<Descriptor, Allocator, false>::traverse_noresize (Argument argument)
 {
   value_type **slot = m_entries;
   value_type **limit = slot + size ();
@@ -803,7 +949,7 @@ template <typename Argument,
 	  int (*Callback) (typename Descriptor::value_type **slot,
 			   Argument argument)>
 void
-hash_table<Descriptor, Allocator>::traverse (Argument argument)
+hash_table<Descriptor, Allocator, false>::traverse (Argument argument)
 {
   size_t size = m_size;
   if (elements () * 8 < size && size > 32)
@@ -816,7 +962,7 @@ hash_table<Descriptor, Allocator>::traverse (Argument argument)
 
 template<typename Descriptor, template<typename Type> class Allocator>
 void
-hash_table<Descriptor, Allocator>::iterator::slide ()
+hash_table<Descriptor, Allocator, false>::iterator::slide ()
 {
   for ( ; m_slot < m_limit; ++m_slot )
     {
@@ -831,8 +977,527 @@ hash_table<Descriptor, Allocator>::iterator::slide ()
 /* Bump the iterator.  */
 
 template<typename Descriptor, template<typename Type> class Allocator>
-inline typename hash_table<Descriptor, Allocator>::iterator &
-hash_table<Descriptor, Allocator>::iterator::operator ++ ()
+inline typename hash_table<Descriptor, Allocator, false>::iterator &
+hash_table<Descriptor, Allocator, false>::iterator::operator ++ ()
+{
+  ++m_slot;
+  slide ();
+  return *this;
+}
+
+/* A partial specialization used when values should be stored directly.  */
+
+template <typename Descriptor,
+	 template<typename Type> class Allocator>
+class hash_table<Descriptor, Allocator, true>
+{
+  typedef typename Descriptor::value_type value_type;
+  typedef typename Descriptor::compare_type compare_type;
+
+public:
+  hash_table (size_t);
+  ~hash_table ();
+
+  /* Current size (in entries) of the hash table.  */
+  size_t size () const { return m_size; }
+
+  /* Return the current number of elements in this hash table. */
+  size_t elements () const { return m_n_elements - m_n_deleted; }
+
+  /* Return the current number of elements in this hash table. */
+  size_t elements_with_deleted () const { return m_n_elements; }
+
+  /* This function clears all entries in the given hash table.  */
+  void empty ();
+
+  /* This function clears a specified SLOT in a hash table.  It is
+     useful when you've already done the lookup and don't want to do it
+     again. */
+
+  void clear_slot (value_type *);
+
+  /* This function searches for a hash table entry equal to the given
+     COMPARABLE element starting with the given HASH value.  It cannot
+     be used to insert or delete an element. */
+  value_type &find_with_hash (const compare_type &, hashval_t);
+
+/* Like find_slot_with_hash, but compute the hash value from the element.  */
+  value_type &find (const value_type &value)
+    {
+      return find_with_hash (value, Descriptor::hash (value));
+    }
+
+  value_type *find_slot (const value_type &value, insert_option insert)
+    {
+      return find_slot_with_hash (value, Descriptor::hash (value), insert);
+    }
+
+  /* This function searches for a hash table slot containing an entry
+     equal to the given COMPARABLE element and starting with the given
+     HASH.  To delete an entry, call this with insert=NO_INSERT, then
+     call clear_slot on the slot returned (possibly after doing some
+     checks).  To insert an entry, call this with insert=INSERT, then
+     write the value you want into the returned slot.  When inserting an
+     entry, NULL may be returned if memory allocation fails. */
+  value_type *find_slot_with_hash (const compare_type &comparable,
+				    hashval_t hash, enum insert_option insert);
+
+  /* This function deletes an element with the given COMPARABLE value
+     from hash table starting with the given HASH.  If there is no
+     matching element in the hash table, this function does nothing. */
+  void remove_elt_with_hash (const compare_type &, hashval_t);
+
+/* Like remove_elt_with_hash, but compute the hash value from the element.  */
+  void remove_elt (const value_type &value)
+    {
+      remove_elt_with_hash (value, Descriptor::hash (value));
+    }
+
+  /* This function scans over the entire hash table calling CALLBACK for
+     each live entry.  If CALLBACK returns false, the iteration stops.
+     ARGUMENT is passed as CALLBACK's second argument. */
+  template <typename Argument,
+	    int (*Callback) (value_type *slot, Argument argument)>
+  void traverse_noresize (Argument argument);
+
+  /* Like traverse_noresize, but does resize the table when it is too empty
+     to improve effectivity of subsequent calls.  */
+  template <typename Argument,
+	    int (*Callback) (value_type *slot, Argument argument)>
+  void traverse (Argument argument);
+
+  class iterator
+  {
+  public:
+    iterator () : m_slot (NULL), m_limit (NULL) {}
+
+    iterator (value_type *slot, value_type *limit) :
+      m_slot (slot), m_limit (limit) {}
+
+    inline value_type &operator * () { return *m_slot; }
+    void slide ();
+    inline iterator &operator ++ ();
+    bool operator != (const iterator &other) const
+      {
+	return m_slot != other.m_slot || m_limit != other.m_limit;
+      }
+
+  private:
+    value_type *m_slot;
+    value_type *m_limit;
+  };
+
+  iterator begin () const
+    {
+      iterator iter (m_entries, m_entries + m_size);
+      iter.slide ();
+      return iter;
+    }
+
+  iterator end () const { return iterator (); }
+
+  double collisions () const
+    {
+      return m_searches ? static_cast <double> (m_collisions) / m_searches : 0;
+    }
+
+private:
+
+  value_type *find_empty_slot_for_expand (hashval_t);
+  void expand ();
+  static bool is_deleted (value_type &v)
+    {
+      return is_deleted_helper<value_type, Descriptor>::call (v);
+    }
+  static bool is_empty (value_type &v)
+    {
+      return is_empty_helper<value_type, Descriptor>::call (v);
+    }
+
+  static void mark_deleted (value_type &v)
+    {
+      return mark_deleted_helper<value_type, Descriptor>::call (v);
+    }
+
+  static void mark_empty (value_type &v)
+    {
+      return mark_empty_helper<value_type, Descriptor>::call (v);
+    }
+
+  /* Table itself.  */
+  typename Descriptor::value_type *m_entries;
+
+  size_t m_size;
+
+  /* Current number of elements including also deleted elements.  */
+  size_t m_n_elements;
+
+  /* Current number of deleted elements in the table.  */
+  size_t m_n_deleted;
+
+  /* The following member is used for debugging. Its value is number
+     of all calls of `htab_find_slot' for the hash table. */
+  unsigned int m_searches;
+
+  /* The following member is used for debugging.  Its value is number
+     of collisions fixed for time of work with the hash table. */
+  unsigned int m_collisions;
+
+  /* Current size (in entries) of the hash table, as an index into the
+     table of primes.  */
+  unsigned int m_size_prime_index;
+};
+
+template<typename Descriptor, template<typename Type> class Allocator>
+hash_table<Descriptor, Allocator, true>::hash_table (size_t size) :
+  m_n_elements (0), m_n_deleted (0), m_searches (0), m_collisions (0)
+{
+  unsigned int size_prime_index;
+
+  size_prime_index = hash_table_higher_prime_index (size);
+  size = prime_tab[size_prime_index].prime;
+
+  m_entries = Allocator <value_type> ::data_alloc (size);
+  gcc_assert (m_entries != NULL);
+  m_size = size;
+  m_size_prime_index = size_prime_index;
+}
+
+template<typename Descriptor, template<typename Type> class Allocator>
+hash_table<Descriptor, Allocator, true>::~hash_table ()
+{
+  for (size_t i = m_size - 1; i < m_size; i--)
+    if (!is_empty (m_entries[i]) && !is_deleted (m_entries[i]))
+      Descriptor::remove (m_entries[i]);
+
+  Allocator <value_type> ::data_free (m_entries);
+}
+
+/* Similar to find_slot, but without several unwanted side effects:
+    - Does not call equal when it finds an existing entry.
+    - Does not change the count of elements/searches/collisions in the
+      hash table.
+   This function also assumes there are no deleted entries in the table.
+   HASH is the hash value for the element to be inserted.  */
+
+template<typename Descriptor, template<typename Type> class Allocator>
+typename Descriptor::value_type *
+hash_table<Descriptor, Allocator, true>
+::find_empty_slot_for_expand (hashval_t hash)
+{
+  hashval_t index = hash_table_mod1 (hash, m_size_prime_index);
+  size_t size = m_size;
+  value_type *slot = m_entries + index;
+  hashval_t hash2;
+
+  if (is_empty (*slot))
+    return slot;
+  else if (is_deleted (*slot))
+    abort ();
+
+  hash2 = hash_table_mod2 (hash, m_size_prime_index);
+  for (;;)
+    {
+      index += hash2;
+      if (index >= size)
+        index -= size;
+
+      slot = m_entries + index;
+      if (is_empty (*slot))
+        return slot;
+      else if (is_deleted (*slot))
+        abort ();
+    }
+}
+
+/* The following function changes size of memory allocated for the
+   entries and repeatedly inserts the table elements.  The occupancy
+   of the table after the call will be about 50%.  Naturally the hash
+   table must already exist.  Remember also that the place of the
+   table entries is changed.  If memory allocation fails, this function
+   will abort.  */
+
+	  template<typename Descriptor, template<typename Type> class Allocator>
+void
+hash_table<Descriptor, Allocator, true>::expand ()
+{
+  value_type *oentries = m_entries;
+  unsigned int oindex = m_size_prime_index;
+  size_t osize = size ();
+  value_type *olimit = oentries + osize;
+  size_t elts = elements ();
+
+  /* Resize only when table after removal of unused elements is either
+     too full or too empty.  */
+  unsigned int nindex;
+  size_t nsize;
+  if (elts * 2 > osize || (elts * 8 < osize && osize > 32))
+    {
+      nindex = hash_table_higher_prime_index (elts * 2);
+      nsize = prime_tab[nindex].prime;
+    }
+  else
+    {
+      nindex = oindex;
+      nsize = osize;
+    }
+
+  value_type *nentries = Allocator <value_type> ::data_alloc (nsize);
+  gcc_assert (nentries != NULL);
+  m_entries = nentries;
+  m_size = nsize;
+  m_size_prime_index = nindex;
+  m_n_elements -= m_n_deleted;
+  m_n_deleted = 0;
+
+  value_type *p = oentries;
+  do
+    {
+      value_type &x = *p;
+
+      if (!is_empty (x) && !is_deleted (x))
+        {
+          value_type *q = find_empty_slot_for_expand (Descriptor::hash (x));
+
+          *q = x;
+        }
+
+      p++;
+    }
+  while (p < olimit);
+
+  Allocator <value_type> ::data_free (oentries);
+}
+
+template<typename Descriptor, template<typename Type> class Allocator>
+void
+hash_table<Descriptor, Allocator, true>::empty ()
+{
+  size_t size = m_size;
+  value_type *entries = m_entries;
+  int i;
+
+  for (i = size - 1; i >= 0; i--)
+    if (!is_empty (entries[i]) && !is_deleted (entries[i]))
+      Descriptor::remove (entries[i]);
+
+  /* Instead of clearing megabyte, downsize the table.  */
+  if (size > 1024*1024 / sizeof (PTR))
+    {
+      int nindex = hash_table_higher_prime_index (1024 / sizeof (PTR));
+      int nsize = prime_tab[nindex].prime;
+
+      Allocator <value_type> ::data_free (m_entries);
+      m_entries = Allocator <value_type> ::data_alloc (nsize);
+      m_size = nsize;
+      m_size_prime_index = nindex;
+    }
+  else
+    memset (entries, 0, size * sizeof (value_type));
+  m_n_deleted = 0;
+  m_n_elements = 0;
+}
+
+/* This function clears a specified SLOT in a hash table.  It is
+   useful when you've already done the lookup and don't want to do it
+   again. */
+
+template<typename Descriptor, template<typename Type> class Allocator>
+void
+hash_table<Descriptor, Allocator, true>::clear_slot (value_type *slot)
+{
+  if (slot < m_entries || slot >= m_entries + size ()
+      || is_empty (*slot) || is_deleted (*slot))
+    abort ();
+
+  Descriptor::remove (*slot);
+
+  mark_deleted (*slot);
+  m_n_deleted++;
+}
+
+/* This function searches for a hash table entry equal to the given
+   COMPARABLE element starting with the given HASH value.  It cannot
+   be used to insert or delete an element. */
+
+template<typename Descriptor, template<typename Type> class Allocator>
+typename Descriptor::value_type &
+hash_table<Descriptor, Allocator, true>
+::find_with_hash (const compare_type &comparable, hashval_t hash)
+{
+  m_searches++;
+  size_t size = m_size;
+  hashval_t index = hash_table_mod1 (hash, m_size_prime_index);
+
+  value_type *entry = &m_entries[index];
+  if (is_empty (*entry)
+      || (!is_deleted (*entry) && Descriptor::equal (*entry, comparable)))
+    return *entry;
+
+  hashval_t hash2 = hash_table_mod2 (hash, m_size_prime_index);
+  for (;;)
+    {
+      m_collisions++;
+      index += hash2;
+      if (index >= size)
+        index -= size;
+
+      entry = &m_entries[index];
+      if (is_empty (*entry)
+          || (!is_deleted (*entry) && Descriptor::equal (*entry, comparable)))
+        return *entry;
+    }
+}
+
+/* This function searches for a hash table slot containing an entry
+   equal to the given COMPARABLE element and starting with the given
+   HASH.  To delete an entry, call this with insert=NO_INSERT, then
+   call clear_slot on the slot returned (possibly after doing some
+   checks).  To insert an entry, call this with insert=INSERT, then
+   write the value you want into the returned slot.  When inserting an
+   entry, NULL may be returned if memory allocation fails. */
+
+template<typename Descriptor, template<typename Type> class Allocator>
+typename Descriptor::value_type *
+hash_table<Descriptor, Allocator, true>
+::find_slot_with_hash (const compare_type &comparable, hashval_t hash,
+		       enum insert_option insert)
+{
+  if (insert == INSERT && m_size * 3 <= m_n_elements * 4)
+    expand ();
+
+  m_searches++;
+
+  value_type *first_deleted_slot = NULL;
+  hashval_t index = hash_table_mod1 (hash, m_size_prime_index);
+  hashval_t hash2 = hash_table_mod2 (hash, m_size_prime_index);
+  value_type *entry = &m_entries[index];
+  size_t size = m_size;
+  if (is_empty (*entry))
+    goto empty_entry;
+  else if (is_deleted (*entry))
+    first_deleted_slot = &m_entries[index];
+  else if (Descriptor::equal (*entry, comparable))
+    return &m_entries[index];
+
+  for (;;)
+    {
+      m_collisions++;
+      index += hash2;
+      if (index >= size)
+	index -= size;
+
+      entry = &m_entries[index];
+      if (is_empty (*entry))
+	goto empty_entry;
+      else if (is_deleted (*entry))
+	{
+	  if (!first_deleted_slot)
+	    first_deleted_slot = &m_entries[index];
+	}
+      else if (Descriptor::equal (*entry, comparable))
+	return &m_entries[index];
+    }
+
+ empty_entry:
+  if (insert == NO_INSERT)
+    return NULL;
+
+  if (first_deleted_slot)
+    {
+      m_n_deleted--;
+      mark_empty (*first_deleted_slot);
+      return first_deleted_slot;
+    }
+
+  m_n_elements++;
+  return &m_entries[index];
+}
+
+/* This function deletes an element with the given COMPARABLE value
+   from hash table starting with the given HASH.  If there is no
+   matching element in the hash table, this function does nothing. */
+
+template<typename Descriptor, template<typename Type> class Allocator>
+void
+hash_table<Descriptor, Allocator, true>
+::remove_elt_with_hash (const compare_type &comparable, hashval_t hash)
+{
+  value_type *slot = find_slot_with_hash (comparable, hash, NO_INSERT);
+  if (is_empty (*slot))
+    return;
+
+  Descriptor::remove (*slot);
+
+  mark_deleted (*slot);
+  m_n_deleted++;
+}
+
+/* This function scans over the entire hash table calling CALLBACK for
+   each live entry.  If CALLBACK returns false, the iteration stops.
+   ARGUMENT is passed as CALLBACK's second argument. */
+
+template<typename Descriptor,
+	  template<typename Type> class Allocator>
+template<typename Argument,
+	  int (*Callback) (typename Descriptor::value_type *slot,
+			   Argument argument)>
+void
+hash_table<Descriptor, Allocator, true>::traverse_noresize (Argument argument)
+{
+  value_type *slot = m_entries;
+  value_type *limit = slot + size ();
+
+  do
+    {
+      value_type &x = *slot;
+
+      if (!is_empty (x) && !is_deleted (x))
+        if (! Callback (slot, argument))
+          break;
+    }
+  while (++slot < limit);
+}
+
+/* Like traverse_noresize, but does resize the table when it is too empty
+   to improve effectivity of subsequent calls.  */
+
+template <typename Descriptor,
+	  template <typename Type> class Allocator>
+template <typename Argument,
+	  int (*Callback) (typename Descriptor::value_type *slot,
+			   Argument argument)>
+void
+hash_table<Descriptor, Allocator, true>::traverse (Argument argument)
+{
+  size_t size = m_size;
+  if (elements () * 8 < size && size > 32)
+    expand ();
+
+  traverse_noresize <Argument, Callback> (argument);
+}
+
+/* Slide down the iterator slots until an active entry is found.  */
+
+template<typename Descriptor, template<typename Type> class Allocator>
+void
+hash_table<Descriptor, Allocator, true>::iterator::slide ()
+{
+  for ( ; m_slot < m_limit; ++m_slot )
+    {
+      value_type &x = *m_slot;
+      if (!is_empty (x) && !is_deleted (x))
+        return;
+    }
+  m_slot = NULL;
+  m_limit = NULL;
+}
+
+/* Bump the iterator.  */
+
+template<typename Descriptor, template<typename Type> class Allocator>
+inline typename hash_table<Descriptor, Allocator, true>::iterator &
+hash_table<Descriptor, Allocator, true>::iterator::operator ++ ()
 {
   ++m_slot;
   slide ();
@@ -846,7 +1511,7 @@ hash_table<Descriptor, Allocator>::iterator::operator ++ ()
 
 #define FOR_EACH_HASH_TABLE_ELEMENT(HTAB, RESULT, TYPE, ITER) \
   for ((ITER) = (HTAB).begin (); \
-       (ITER) != (HTAB).end () ? (RESULT = &*(ITER) , true) : false; \
+       (ITER) != (HTAB).end () ? (RESULT = *(ITER) , true) : false; \
        ++(ITER))
 
 #endif /* TYPED_HASHTAB_H */
diff --git a/gcc/tree-browser.c b/gcc/tree-browser.c
index 8c03550..2a4db1b 100644
--- a/gcc/tree-browser.c
+++ b/gcc/tree-browser.c
@@ -102,22 +102,13 @@ static tree TB_history_prev (void);
 void browse_tree (tree);
 
 /* Hashtable helpers.  */
-struct tree_upper_hasher : typed_noop_remove <tree_node>
+struct tree_upper_hasher : pointer_hash<tree_node>
 {
-  typedef tree_node value_type;
-  typedef tree_node compare_type;
-  static inline hashval_t hash (const value_type *);
-  static inline bool equal (const value_type *, const compare_type *);
+  static inline bool equal (const value_type &, const compare_type &);
 };
 
-inline hashval_t
-tree_upper_hasher::hash (const value_type *v)
-{
-  return pointer_hash <value_type>::hash (v);
-}
-
 inline bool
-tree_upper_hasher::equal (const value_type *parent, const compare_type *node)
+tree_upper_hasher::equal (const value_type &parent, const compare_type &node)
 {
   if (parent == NULL || node == NULL)
     return 0;
diff --git a/gcc/tree-complex.c b/gcc/tree-complex.c
index 7b0115d..3ed403a 100644
--- a/gcc/tree-complex.c
+++ b/gcc/tree-complex.c
@@ -83,10 +83,9 @@ static vec<tree> complex_ssa_name_components;
 static tree
 cvc_lookup (unsigned int uid)
 {
-  struct int_tree_map *h, in;
+  struct int_tree_map in;
   in.uid = uid;
-  h = complex_variable_components->find_with_hash (&in, uid);
-  return h ? h->to : NULL;
+  return complex_variable_components->find_with_hash (in, uid).to;
 }
 
 /* Insert the pair UID, TO into the complex_variable_components hashtable.  */
@@ -94,14 +93,13 @@ cvc_lookup (unsigned int uid)
 static void
 cvc_insert (unsigned int uid, tree to)
 {
-  struct int_tree_map *h;
-  int_tree_map **loc;
+  int_tree_map h;
+  int_tree_map *loc;
 
-  h = XNEW (struct int_tree_map);
-  h->uid = uid;
-  h->to = to;
+  h.uid = uid;
   loc = complex_variable_components->find_slot_with_hash (h, uid, INSERT);
-  *loc = h;
+  loc->uid = uid;
+  loc->to = to;
 }
 
 /* Return true if T is not a zero constant.  In the case of real values,
diff --git a/gcc/tree-hasher.h b/gcc/tree-hasher.h
index 6b28008..ae56a84 100644
--- a/gcc/tree-hasher.h
+++ b/gcc/tree-hasher.h
@@ -30,28 +30,37 @@ struct int_tree_map {
 
 /* Hashtable helpers.  */
 
-struct int_tree_hasher : typed_free_remove <int_tree_map>
+struct int_tree_hasher
 {
   typedef int_tree_map value_type;
   typedef int_tree_map compare_type;
-  static inline hashval_t hash (const value_type *);
-  static inline bool equal (const value_type *, const compare_type *);
+  typedef int store_values_directly;
+  static inline hashval_t hash (const value_type &);
+  static inline bool equal (const value_type &, const compare_type &);
+  static bool is_deleted (const value_type &v)
+    {
+      return v.to == reinterpret_cast<tree> (1);
+    }
+  static void mark_deleted (value_type &v) { v.to = reinterpret_cast<tree> (0x1); }
+  static bool is_empty (const value_type &v) { return v.to == NULL; }
+  static void mark_empty (value_type &v) { v.to = NULL; }
+  static void remove (value_type &) {}
 };
 
 /* Hash a UID in a int_tree_map.  */
 
 inline hashval_t
-int_tree_hasher::hash (const value_type *item)
+int_tree_hasher::hash (const value_type &item)
 {
-  return item->uid;
+  return item.uid;
 }
 
 /* Return true if the uid in both int tree maps are equal.  */
 
 inline bool
-int_tree_hasher::equal (const value_type *a, const compare_type *b)
+int_tree_hasher::equal (const value_type &a, const compare_type &b)
 {
-  return (a->uid == b->uid);
+  return (a.uid == b.uid);
 }
 
 typedef hash_table <int_tree_hasher> int_tree_htab_type;
diff --git a/gcc/tree-into-ssa.c b/gcc/tree-into-ssa.c
index 1cdcc2f..96255f9 100644
--- a/gcc/tree-into-ssa.c
+++ b/gcc/tree-into-ssa.c
@@ -203,20 +203,21 @@ typedef struct var_info_d *var_info_p;
 
 struct var_info_hasher : typed_free_remove <var_info_d>
 {
-  typedef var_info_d value_type;
-  typedef var_info_d compare_type;
-  static inline hashval_t hash (const value_type *);
-  static inline bool equal (const value_type *, const compare_type *);
+  typedef var_info_d *value_type;
+  typedef var_info_d *compare_type;
+  typedef int store_values_directly;
+  static inline hashval_t hash (const value_type &);
+  static inline bool equal (const value_type &, const compare_type &);
 };
 
 inline hashval_t
-var_info_hasher::hash (const value_type *p)
+var_info_hasher::hash (const value_type &p)
 {
   return DECL_UID (p->var);
 }
 
 inline bool
-var_info_hasher::equal (const value_type *p1, const compare_type *p2)
+var_info_hasher::equal (const value_type &p1, const compare_type &p2)
 {
   return p1->var == p2->var;
 }
diff --git a/gcc/tree-parloops.c b/gcc/tree-parloops.c
index 3ef4aa6..0c486bb 100644
--- a/gcc/tree-parloops.c
+++ b/gcc/tree-parloops.c
@@ -489,8 +489,6 @@ take_address_of (tree obj, tree type, edge entry,
 		 int_tree_htab_type *decl_address, gimple_stmt_iterator *gsi)
 {
   int uid;
-  int_tree_map **dslot;
-  struct int_tree_map ielt, *nielt;
   tree *var_p, name, addr;
   gimple stmt;
   gimple_seq stmts;
@@ -511,9 +509,10 @@ take_address_of (tree obj, tree type, edge entry,
      in the address and share it for all accesses and addresses based
      on it.  */
   uid = DECL_UID (TREE_OPERAND (TREE_OPERAND (*var_p, 0), 0));
-  ielt.uid = uid;
-  dslot = decl_address->find_slot_with_hash (&ielt, uid, INSERT);
-  if (!*dslot)
+  int_tree_map elt;
+  elt.uid = uid;
+  int_tree_map *slot = decl_address->find_slot (elt, INSERT);
+  if (!slot->to)
     {
       if (gsi == NULL)
 	return NULL;
@@ -527,13 +526,11 @@ take_address_of (tree obj, tree type, edge entry,
       stmt = gimple_build_assign (name, addr);
       gsi_insert_on_edge_immediate (entry, stmt);
 
-      nielt = XNEW (struct int_tree_map);
-      nielt->uid = uid;
-      nielt->to = name;
-      *dslot = nielt;
+      slot->uid = uid;
+      slot->to = name;
     }
   else
-    name = (*dslot)->to;
+    name = slot->to;
 
   /* Express the address in terms of the canonical SSA name.  */
   TREE_OPERAND (*var_p, 0) = name;
@@ -822,10 +819,10 @@ separate_decls_in_region_name (tree name, name_to_copy_table_type *name_copies,
 {
   tree copy, var, var_copy;
   unsigned idx, uid, nuid;
-  struct int_tree_map ielt, *nielt;
+  struct int_tree_map ielt;
   struct name_to_copy_elt elt, *nelt;
   name_to_copy_elt **slot;
-  int_tree_map **dslot;
+  int_tree_map *dslot;
 
   if (TREE_CODE (name) != SSA_NAME)
     return name;
@@ -858,29 +855,25 @@ separate_decls_in_region_name (tree name, name_to_copy_table_type *name_copies,
 
   uid = DECL_UID (var);
   ielt.uid = uid;
-  dslot = decl_copies->find_slot_with_hash (&ielt, uid, INSERT);
-  if (!*dslot)
+  dslot = decl_copies->find_slot_with_hash (ielt, uid, INSERT);
+  if (!dslot->to)
     {
       var_copy = create_tmp_var (TREE_TYPE (var), get_name (var));
       DECL_GIMPLE_REG_P (var_copy) = DECL_GIMPLE_REG_P (var);
-      nielt = XNEW (struct int_tree_map);
-      nielt->uid = uid;
-      nielt->to = var_copy;
-      *dslot = nielt;
+      dslot->uid = uid;
+      dslot->to = var_copy;
 
       /* Ensure that when we meet this decl next time, we won't duplicate
          it again.  */
       nuid = DECL_UID (var_copy);
       ielt.uid = nuid;
-      dslot = decl_copies->find_slot_with_hash (&ielt, nuid, INSERT);
-      gcc_assert (!*dslot);
-      nielt = XNEW (struct int_tree_map);
-      nielt->uid = nuid;
-      nielt->to = var_copy;
-      *dslot = nielt;
+      dslot = decl_copies->find_slot_with_hash (ielt, nuid, INSERT);
+      gcc_assert (!dslot->to);
+      dslot->uid = nuid;
+      dslot->to = var_copy;
     }
   else
-    var_copy = ((struct int_tree_map *) *dslot)->to;
+    var_copy = dslot->to;
 
   replace_ssa_name_symbol (copy, var_copy);
   return copy;
@@ -944,7 +937,7 @@ separate_decls_in_region_debug (gimple stmt,
   struct int_tree_map ielt;
   struct name_to_copy_elt elt;
   name_to_copy_elt **slot;
-  int_tree_map **dslot;
+  int_tree_map *dslot;
 
   if (gimple_debug_bind_p (stmt))
     var = gimple_debug_bind_get_var (stmt);
@@ -956,13 +949,13 @@ separate_decls_in_region_debug (gimple stmt,
     return true;
   gcc_assert (DECL_P (var) && SSA_VAR_P (var));
   ielt.uid = DECL_UID (var);
-  dslot = decl_copies->find_slot_with_hash (&ielt, ielt.uid, NO_INSERT);
+  dslot = decl_copies->find_slot_with_hash (ielt, ielt.uid, NO_INSERT);
   if (!dslot)
     return true;
   if (gimple_debug_bind_p (stmt))
-    gimple_debug_bind_set_var (stmt, ((struct int_tree_map *) *dslot)->to);
+    gimple_debug_bind_set_var (stmt, dslot->to);
   else if (gimple_debug_source_bind_p (stmt))
-    gimple_debug_source_bind_set_var (stmt, ((struct int_tree_map *) *dslot)->to);
+    gimple_debug_source_bind_set_var (stmt, dslot->to);
 
   FOR_EACH_PHI_OR_STMT_USE (use, stmt, oi, SSA_OP_USE)
   {
diff --git a/gcc/tree-ssa-dom.c b/gcc/tree-ssa-dom.c
index 6c581ba..61e75b6 100644
--- a/gcc/tree-ssa-dom.c
+++ b/gcc/tree-ssa-dom.c
@@ -158,21 +158,22 @@ static void free_expr_hash_elt (void *);
 
 struct expr_elt_hasher
 {
-  typedef expr_hash_elt value_type;
-  typedef expr_hash_elt compare_type;
-  static inline hashval_t hash (const value_type *);
-  static inline bool equal (const value_type *, const compare_type *);
-  static inline void remove (value_type *);
+  typedef expr_hash_elt *value_type;
+  typedef expr_hash_elt *compare_type;
+  typedef int store_values_directly;
+  static inline hashval_t hash (const value_type &);
+  static inline bool equal (const value_type &, const compare_type &);
+  static inline void remove (value_type &);
 };
 
 inline hashval_t
-expr_elt_hasher::hash (const value_type *p)
+expr_elt_hasher::hash (const value_type &p)
 {
   return p->hash;
 }
 
 inline bool
-expr_elt_hasher::equal (const value_type *p1, const compare_type *p2)
+expr_elt_hasher::equal (const value_type &p1, const compare_type &p2)
 {
   gimple stmt1 = p1->stmt;
   const struct hashable_expr *expr1 = &p1->expr;
@@ -211,7 +212,7 @@ expr_elt_hasher::equal (const value_type *p1, const compare_type *p2)
 /* Delete an expr_hash_elt and reclaim its storage.  */
 
 inline void
-expr_elt_hasher::remove (value_type *element)
+expr_elt_hasher::remove (value_type &element)
 {
   free_expr_hash_elt (element);
 }
diff --git a/gcc/tree-ssa-reassoc.c b/gcc/tree-ssa-reassoc.c
index 4d0d6c2..4903f48 100644
--- a/gcc/tree-ssa-reassoc.c
+++ b/gcc/tree-ssa-reassoc.c
@@ -1023,32 +1023,36 @@ static vec<oecount> cvec;
 
 /* Oecount hashtable helpers.  */
 
-struct oecount_hasher : typed_noop_remove <void>
+struct oecount_hasher
 {
-  /* Note that this hash table stores integers, not pointers.
-     So, observe the casting in the member functions.  */
-  typedef void value_type;
-  typedef void compare_type;
-  static inline hashval_t hash (const value_type *);
-  static inline bool equal (const value_type *, const compare_type *);
+  typedef int value_type;
+  typedef int compare_type;
+  typedef int store_values_directly;
+  static inline hashval_t hash (const value_type &);
+  static inline bool equal (const value_type &, const compare_type &);
+  static bool is_deleted (int &v) { return v == 1; }
+  static void mark_deleted (int &e) { e = 1; }
+  static bool is_empty (int &v) { return v == 0; }
+  static void mark_empty (int &e) { e = 0; }
+  static void remove (int &) {}
 };
 
 /* Hash function for oecount.  */
 
 inline hashval_t
-oecount_hasher::hash (const value_type *p)
+oecount_hasher::hash (const value_type &p)
 {
-  const oecount *c = &cvec[(size_t)p - 42];
+  const oecount *c = &cvec[p - 42];
   return htab_hash_pointer (c->op) ^ (hashval_t)c->oecode;
 }
 
 /* Comparison function for oecount.  */
 
 inline bool
-oecount_hasher::equal (const value_type *p1, const compare_type *p2)
+oecount_hasher::equal (const value_type &p1, const compare_type &p2)
 {
-  const oecount *c1 = &cvec[(size_t)p1 - 42];
-  const oecount *c2 = &cvec[(size_t)p2 - 42];
+  const oecount *c1 = &cvec[p1 - 42];
+  const oecount *c2 = &cvec[p2 - 42];
   return (c1->oecode == c2->oecode
 	  && c1->op == c2->op);
 }
@@ -1473,23 +1477,23 @@ undistribute_ops_list (enum tree_code opcode,
       FOR_EACH_VEC_ELT (subops[i], j, oe1)
 	{
 	  oecount c;
-	  void **slot;
-	  size_t idx;
+	  int *slot;
+	  int idx;
 	  c.oecode = oecode;
 	  c.cnt = 1;
 	  c.id = next_oecount_id++;
 	  c.op = oe1->op;
 	  cvec.safe_push (c);
 	  idx = cvec.length () + 41;
-	  slot = ctable.find_slot ((void *)idx, INSERT);
+	  slot = ctable.find_slot (idx, INSERT);
 	  if (!*slot)
 	    {
-	      *slot = (void *)idx;
+	      *slot = idx;
 	    }
 	  else
 	    {
 	      cvec.pop ();
-	      cvec[(size_t)*slot - 42].cnt++;
+	      cvec[*slot - 42].cnt++;
 	    }
 	}
     }
diff --git a/gcc/tree-vectorizer.c b/gcc/tree-vectorizer.c
index 4d30cfa..6092355 100644
--- a/gcc/tree-vectorizer.c
+++ b/gcc/tree-vectorizer.c
@@ -550,14 +550,14 @@ vectorize_loops (void)
       for (hash_table<simd_array_to_simduid>::iterator iter
 	   = simd_array_to_simduid_htab->begin ();
 	   iter != simd_array_to_simduid_htab->end (); ++iter)
-	if ((*iter).simduid != -1U)
+	if ((*iter)->simduid != -1U)
 	  {
-	    tree decl = (*iter).decl;
+	    tree decl = (*iter)->decl;
 	    int vf = 1;
 	    if (simduid_to_vf_htab)
 	      {
 		simduid_to_vf *p = NULL, data;
-		data.simduid = (*iter).simduid;
+		data.simduid = (*iter)->simduid;
 		p = simduid_to_vf_htab->find (&data);
 		if (p)
 		  vf = p->vf;