This patch extracts approved portions of the hash_table patches to the...

This patch extracts approved portions of the hash_table patches to
the cxx-conversion branch for files not under gcc/config.

Update various hash tables from htab_t to hash_table.
Modify types and calls to match.

* tree-ssa-coalesce.c'coalesce_list_d.list from htab_t to hash_table.

Fold coalesce_pair_map_hash and coalesce_pair_map_eq into new
struct coalesce_pair_hasher.

Removed struct coalesce_pair_iterator, as did not meet the hash_table
iterator interface and it provided no significant code reduction.
This leads to a change in the implementation of FOR_EACH_PARTITION_PAIR.

* statistics.c'statistics_hashes

Fold hash_statistics_eq into new struct stats_counter_hasher.

* hash-table.h'hash_table

Add documentation.
Add nested class iterator and methods to hash_table.
Add FOR_EACH_HASH_TABLE_ELEMENT implemented with those iterators.
Change uses of FOR_EACH_HTAB_ELEMENT to FOR_EACH_HASH_TABLE_ELEMENT.

* tree-ssa-sccvn.c'vn_tables_s.nary

Fold vn_nary_op_hash, vn_nary_op_eq into new struct vn_nary_op_hasher.
Add typedef vn_nary_op_table_type.
Add typedef vn_nary_op_iterator_type.

* tree-ssa-sccvn.c'vn_tables_s.phis

Fold vn_phi_hash, free_phi into new struct vn_phi_hasher.
Add typedef vn_phi_table_type.
Add typedef vn_phi_iterator_type.

* tree-ssa-sccvn.c'vn_tables_s.references

Fold vn_reference_hash, vn_reference_op_eq, free_reference
  into new struct vn_reference_hasher.
Add typedef vn_reference_table_type.
Add typedef vn_reference_iterator_type.

* tree-ssa-sccvn.c'constant_value_ids

Fold vn_constant_hash, vn_constant_eq into new struct vn_constant_hasher.

* tree-into-ssa.c'var_infos

Fold var_info_hash, var_info_eq into new struct var_info_hasher.

* tree-vectorizer.h'_loop_vec_info::peeling_htab

* tree-vectorizer.h

New struct peel_info_hasher.

* tree-vect-loop.c

Update dependent calls and types to match.

* tree-vect-data-refs.c

Fold vect_peeling_hash and vect_peeling_hash_eq into struct peel_info_hasher.

* tree-ssa-reassoc.c'undistribute_ops_list::ctable

Fold oecount_hash and oecount_eq into new struct oecount_hasher.

* tree-ssa-loop-im.c'memory_accesses.refs

Fold memref_hash and memref_eq into new struct mem_ref_hasher.

Tested on x86_64.


Index: gcc/ChangeLog

2013-04-23  Lawrence Crowl  <crowl@google.com>

	* Makefile.in: Update as needed below.

	* hash-table.h (class hash_table):
	Correct many methods with parameter types compare_type to the correct
	value_type.  (Correct code was unlikely to notice the change.)
	(hash_table::elements_with_deleted) New.
	(class hashtable::iterator): New.
	(hashtable::begin()): New.
	(hashtable::end()): New.
	(FOR_EACH_HASH_TABLE_ELEMENT): New.

	* statistics.c (statistics_hashes):
	Change type to hash_table.  Update dependent calls and types.

	* tree-into-ssa.c (var_infos):
	Change type to hash_table.  Update dependent calls and types.

	* tree-ssa-coalesce.c (struct coalesce_list_d.list):
	Change type to hash_table.  Update dependent calls and types.

	* tree-ssa-loop-im.c (struct mem_ref.refs):
	Change type to hash_table.  Update dependent calls and types.

	* tree-ssa-reassoc.c (undistribute_ops_list::ctable):
	Change type to hash_table.  Update dependent calls and types.

	* tree-ssa-sccvn.c (vn_tables_s::nary):
	Change type to hash_table.  Update dependent calls and types.
	(vn_tables_s::phis): Likewise.
	(vn_tables_s::references): Likewise.

	* tree-ssa-sccvn.h (vn_nary_op_eq): Update parameter and return types.
	(vn_reference_eq): Update parameter and return types.

	* tree-ssa-structalias.c (pointer_equiv_class_table):
	Change type to hash_table.  Update dependent calls and types.
	(location_equiv_class_table): Likewise.

	* tree-vect-data-refs.c: Consequential changes for making
	peeling a hash_table.

	* tree-vect-loop.c (new_loop_vec_info): Dependent hash_table update.
	(destroy_loop_vec_info): Dependent hash_table update.

	* tree-vectorizer.h (peeling_htab):
	Change type to hash_table.  Update dependent calls and types.

From-SVN: r198213

1 files changed, 193 insertions, 14 deletions

diff --git a/gcc/hash-table.h b/gcc/hash-table.h
index 206423d..0063778 100644
--- a/gcc/hash-table.h
+++ b/gcc/hash-table.h
@@ -155,6 +155,47 @@ along with GCC; see the file COPYING3.  If not see
 
       hash_table <pointer_hash <whatever_type>> whatever_type_hash_table;
 
+
+   HASH TABLE ITERATORS
+
+   The hash table provides standard C++ iterators.  For example, consider a
+   hash table of some_info.  We wish to consume each element of the table:
+
+      extern void consume (some_info *);
+
+   We define a convenience typedef and the hash table:
+
+      typedef hash_table <some_info_hasher> info_table_type;
+      info_table_type info_table;
+
+   Then we write the loop in typical C++ style:
+
+      for (info_table_type::iterator iter = info_table.begin ();
+           iter != info_table.end ();
+           ++iter)
+        if ((*iter).status == INFO_READY)
+          consume (&*iter);
+
+   Or with common sub-expression elimination:
+
+      for (info_table_type::iterator iter = info_table.begin ();
+           iter != info_table.end ();
+           ++iter)
+        {
+          some_info &elem = *iter;
+          if (elem.status == INFO_READY)
+            consume (&elem);
+        }
+
+   One can also use a more typical GCC style:
+
+      typedef some_info *some_info_p;
+      some_info *elem_ptr;
+      info_table_type::iterator iter;
+      FOR_EACH_HASH_TABLE_ELEMENT (info_table, elem_ptr, some_info_p, iter)
+        if (elem_ptr->status == INFO_READY)
+          consume (elem_ptr);
+
 */
 
 
@@ -368,6 +409,20 @@ public:
   typedef typename Descriptor::value_type value_type;
   typedef typename Descriptor::compare_type compare_type;
 
+  class iterator
+  {
+  public:
+    inline iterator ();
+    inline iterator (value_type **, value_type **);
+    inline value_type &operator * ();
+    void slide ();
+    inline iterator &operator ++ ();
+    inline bool operator != (const iterator &) const;
+  private:
+    value_type **slot_;
+    value_type **limit_;
+  };
+
 private:
   hash_table_control <value_type> *htab;
 
@@ -379,19 +434,19 @@ public:
   void create (size_t initial_slots);
   bool is_created ();
   void dispose ();
-  value_type *find (const compare_type *comparable);
+  value_type *find (const value_type *value);
   value_type *find_with_hash (const compare_type *comparable, hashval_t hash);
-  value_type **find_slot (const compare_type *comparable,
-			  enum insert_option insert);
+  value_type **find_slot (const value_type *value, enum insert_option insert);
   value_type **find_slot_with_hash (const compare_type *comparable,
 				    hashval_t hash, enum insert_option insert);
   void empty ();
   void clear_slot (value_type **slot);
-  void remove_elt (const compare_type *comparable);
+  void remove_elt (const value_type *value);
   void remove_elt_with_hash (const compare_type *comparable, hashval_t hash);
-  size_t size();
-  size_t elements();
-  double collisions();
+  size_t size ();
+  size_t elements ();
+  size_t elements_with_deleted ();
+  double collisions ();
 
   template <typename Argument,
 	    int (*Callback) (value_type **slot, Argument argument)>
@@ -400,6 +455,9 @@ public:
   template <typename Argument,
 	    int (*Callback) (value_type **slot, Argument argument)>
   void traverse (Argument argument);
+
+  iterator begin();
+  iterator end();
 };
 
 
@@ -430,9 +488,9 @@ hash_table <Descriptor, Allocator>::is_created ()
 template <typename Descriptor,
 	  template <typename Type> class Allocator>
 inline typename Descriptor::value_type *
-hash_table <Descriptor, Allocator>::find (const compare_type *comparable)
+hash_table <Descriptor, Allocator>::find (const value_type *value)
 {
-  return find_with_hash (comparable, Descriptor::hash (comparable));
+  return find_with_hash (value, Descriptor::hash (value));
 }
 
 
@@ -442,9 +500,9 @@ template <typename Descriptor,
 	  template <typename Type> class Allocator>
 inline typename Descriptor::value_type **
 hash_table <Descriptor, Allocator>
-::find_slot (const compare_type *comparable, enum insert_option insert)
+::find_slot (const value_type *value, enum insert_option insert)
 {
-  return find_slot_with_hash (comparable, Descriptor::hash (comparable), insert);
+  return find_slot_with_hash (value, Descriptor::hash (value), insert);
 }
 
 
@@ -453,9 +511,9 @@ hash_table <Descriptor, Allocator>
 template <typename Descriptor,
 	  template <typename Type> class Allocator>
 inline void
-hash_table <Descriptor, Allocator>::remove_elt (const compare_type *comparable)
+hash_table <Descriptor, Allocator>::remove_elt (const value_type *value)
 {
-  remove_elt_with_hash (comparable, Descriptor::hash (comparable));
+  remove_elt_with_hash (value, Descriptor::hash (value));
 }
 
 
@@ -475,12 +533,23 @@ hash_table <Descriptor, Allocator>::size()
 template <typename Descriptor,
 	  template <typename Type> class Allocator>
 inline size_t
-hash_table <Descriptor, Allocator>::elements()
+hash_table <Descriptor, Allocator>::elements ()
 {
   return htab->n_elements - htab->n_deleted;
 }
 
 
+/* Return the current number of elements in this hash table. */
+
+template <typename Descriptor,
+	  template <typename Type> class Allocator>
+inline size_t
+hash_table <Descriptor, Allocator>::elements_with_deleted ()
+{
+  return htab->n_elements;
+}
+
+
   /* Return the fraction of fixed collisions during all work with given
      hash table. */
 
@@ -881,4 +950,114 @@ hash_table <Descriptor, Allocator>::traverse (Argument argument)
   traverse_noresize <Argument, Callback> (argument);
 }
 
+
+/* Iterator definitions.  */
+
+/* The default constructor produces the end value.  */
+
+template <typename Descriptor,
+	  template <typename Type> class Allocator>
+inline
+hash_table <Descriptor, Allocator>::iterator::iterator ()
+: slot_ (NULL), limit_ (NULL)
+{
+}
+
+/* The parameterized constructor produces the begin value.  */
+
+template <typename Descriptor,
+	  template <typename Type> class Allocator>
+inline
+hash_table <Descriptor, Allocator>::iterator::iterator
+   (value_type **slot, value_type **limit)
+: slot_ (slot), limit_ (limit)
+{
+}
+
+/* Obtain the element.  */
+
+template <typename Descriptor,
+	  template <typename Type> class Allocator>
+inline typename hash_table <Descriptor, Allocator>::value_type &
+hash_table <Descriptor, Allocator>::iterator::operator * ()
+{
+  return **slot_;
+}
+
+/* Slide down the iterator slots until an active entry is found.  */
+
+template <typename Descriptor,
+	  template <typename Type> class Allocator>
+void
+hash_table <Descriptor, Allocator>::iterator::slide ()
+{
+  for ( ; slot_ < limit_; ++slot_ )
+    {
+      value_type *x = *slot_;
+      if (x != HTAB_EMPTY_ENTRY && x != HTAB_DELETED_ENTRY)
+        return;
+    }
+  slot_ = NULL;
+  limit_ = NULL;
+}
+
+/* Bump the iterator.  */
+
+template <typename Descriptor,
+	  template <typename Type> class Allocator>
+inline typename hash_table <Descriptor, Allocator>::iterator &
+hash_table <Descriptor, Allocator>::iterator::operator ++ ()
+{
+  ++slot_;
+  slide ();
+  return *this;
+}
+
+/* Compare iterators.  */
+
+template <typename Descriptor,
+	  template <typename Type> class Allocator>
+inline bool
+hash_table <Descriptor, Allocator>::iterator::
+  operator != (const iterator &other) const
+{
+  return slot_ != other.slot_ || limit_ != other.limit_;
+}
+
+/* Hash table iterator producers.  */
+
+/* The beginning of a hash table iteration.  */
+
+template <typename Descriptor,
+	  template <typename Type> class Allocator>
+inline typename hash_table <Descriptor, Allocator>::iterator
+hash_table <Descriptor, Allocator>::begin ()
+{
+  iterator hti (htab->entries, htab->entries + htab->size);
+  hti.slide ();
+  return hti;
+}
+
+/* The end of a hash table iteration.  */
+
+template <typename Descriptor,
+	  template <typename Type> class Allocator>
+inline typename hash_table <Descriptor, Allocator>::iterator
+hash_table <Descriptor, Allocator>::end ()
+{
+  return iterator ();
+}
+
+/* Iterate through the elements of hash_table HTAB,
+   using hash_table <....>::iterator ITER,
+   storing each element in RESULT, which is of type TYPE.
+
+   This macro has this form for compatibility with the
+   FOR_EACH_HTAB_ELEMENT currently defined in tree-flow.h.  */
+
+#define FOR_EACH_HASH_TABLE_ELEMENT(HTAB, RESULT, TYPE, ITER) \
+  for ((ITER) = (HTAB).begin (); \
+       (ITER) != (HTAB).end () ? (RESULT = &*(ITER) , true) : false; \
+       ++(ITER))
+
 #endif /* TYPED_HASHTAB_H */