This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[PATCH 2/N] allow storing values directly in hash tables
- From: tsaunders at mozilla dot com
- To: gcc-patches at gcc dot gnu dot org
- Cc: Trevor Saunders <tsaunders at mozilla dot com>
- Date: Fri, 20 Jun 2014 06:52:17 -0400
- Subject: [PATCH 2/N] allow storing values directly in hash tables
- Authentication-results: sourceware.org; auth=none
- References: <1403261538-884-1-git-send-email-tsaunders at mozilla dot com>
From: Trevor Saunders <tsaunders@mozilla.com>
Hi,
this patch allows you to define the type the hash table stores as elements
instead of the type elements point at by having your hash descriptor define the
type store_values_directly. It turns out trying to implement both cases with
the same code is really confusing, so I ended up providing one partial
specialization for each case. Its a lot of coppying, but I'm hoping the next
patch will get rid of many direct users of hash_table, and the rest can all get
converted to tell the hash table the type entries should have at which point
the dupplication can be removed.
bootstrapped + regtested without regression on x86_64-unknown-linux-gnu, ok?
Trev
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.
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 e553e28..0ad22c7 100644
--- a/gcc/tree-vectorizer.c
+++ b/gcc/tree-vectorizer.c
@@ -548,14 +548,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;
--
2.0.0