[08/12] Add common traits for integer hash keys

[Richard Sandiford <richard.sandiford@arm.com>]

Several places define hash traits for integers, using particular integer
values as "empty" and "deleted" markers.  This patch defines them in terms
of a single int_hash class.

I also needed to extend gengtype to accept "+" in template arguments.


gcc/
	* gengtype-parse.c (require_template_declaration): Allow '+' in
	template parameters.  Consolidate cases.
	* hash-traits.h (int_hash): New class.
	* alias.c (alias_set_hash): New structure.
	(alias_set_traits): Use it.
	* symbol-summary.h (function_summary::map_hash): New class.
	(function_summary::summary_hashmap_traits): Use it.
	* tree-inline.h (dependence_hash): New class.
	(dependence_hasher): Use it.
	* tree-ssa-reassoc.c (oecount_hasher): Use int_hash.
	* value-prof.c (profile_id_hash): New class.
	(profile_id_traits): Use it.

Index: gcc/gengtype-parse.c
===================================================================
--- gcc/gengtype-parse.c	2015-06-23 15:50:56.686110247 +0100
+++ gcc/gengtype-parse.c	2015-06-23 15:50:56.678110339 +0100
@@ -274,17 +274,13 @@ require_template_declaration (const char
 	  str = concat (str, "enum ", (char *) 0);
 	  continue;
 	}
-      if (token () == NUM)
+      if (token () == NUM
+	  || token () == ':'
+	  || token () == '+')
 	{
 	  str = concat (str, advance (), (char *) 0);
 	  continue;
 	}
-      if (token () == ':')
-	{
-	  advance ();
-	  str = concat (str, ":", (char *) 0);
-	  continue;
-	}
       if (token () == '<')
 	{
 	  advance ();
Index: gcc/hash-traits.h
===================================================================
--- gcc/hash-traits.h	2015-06-23 15:50:56.686110247 +0100
+++ gcc/hash-traits.h	2015-06-23 15:50:56.674110387 +0100
@@ -57,6 +57,68 @@ typed_noop_remove <Type>::remove (Type &
 }
 
 
+/* Hasher for integer type Type in which Empty is a spare value that can be
+   used to mark empty slots.  If Deleted != Empty then Deleted is another
+   spare value that can be used for deleted slots; if Deleted == Empty then
+   hash table entries cannot be deleted.  */
+
+template <typename Type, Type Empty, Type Deleted = Empty>
+struct int_hash : typed_noop_remove <Type>
+{
+  typedef Type value_type;
+  typedef Type compare_type;
+
+  static inline hashval_t hash (value_type);
+  static inline bool equal (value_type existing, value_type candidate);
+  static inline void mark_deleted (Type &);
+  static inline void mark_empty (Type &);
+  static inline bool is_deleted (Type);
+  static inline bool is_empty (Type);
+};
+
+template <typename Type, Type Empty, Type Deleted>
+inline hashval_t
+int_hash <Type, Empty, Deleted>::hash (value_type x)
+{
+  return x;
+}
+
+template <typename Type, Type Empty, Type Deleted>
+inline bool
+int_hash <Type, Empty, Deleted>::equal (value_type x, value_type y)
+{
+  return x == y;
+}
+
+template <typename Type, Type Empty, Type Deleted>
+inline void
+int_hash <Type, Empty, Deleted>::mark_deleted (Type &x)
+{
+  gcc_assert (Empty != Deleted);
+  x = Deleted;
+}
+
+template <typename Type, Type Empty, Type Deleted>
+inline void
+int_hash <Type, Empty, Deleted>::mark_empty (Type &x)
+{
+  x = Empty;
+}
+
+template <typename Type, Type Empty, Type Deleted>
+inline bool
+int_hash <Type, Empty, Deleted>::is_deleted (Type x)
+{
+  return Empty != Deleted && x == Deleted;
+}
+
+template <typename Type, Type Empty, Type Deleted>
+inline bool
+int_hash <Type, Empty, Deleted>::is_empty (Type x)
+{
+  return x == Empty;
+}
+
 /* Pointer hasher based on pointer equality.  Other types of pointer hash
    can inherit this and override the hash and equal functions with some
    other form of equality (such as string equality).  */
Index: gcc/alias.c
===================================================================
--- gcc/alias.c	2015-06-23 15:50:56.686110247 +0100
+++ gcc/alias.c	2015-06-23 15:50:56.678110339 +0100
@@ -143,31 +143,8 @@ Software Foundation; either version 3, o
    However, this is no actual entry for alias set zero.  It is an
    error to attempt to explicitly construct a subset of zero.  */
 
-struct alias_set_traits : default_hashmap_traits
-{
-  template<typename T>
-  static bool
-  is_empty (T &e)
-  {
-    return e.m_key == INT_MIN;
-  }
-
-  template<typename  T>
-  static bool
-  is_deleted (T &e)
-  {
-    return e.m_key == (INT_MIN + 1);
-  }
-
-  template<typename T> static void mark_empty (T &e) { e.m_key = INT_MIN; }
-
-  template<typename T>
-  static void
-  mark_deleted (T &e)
-  {
-    e.m_key = INT_MIN + 1;
-  }
-};
+struct alias_set_hash : int_hash <int, INT_MIN, INT_MIN + 1> {};
+struct alias_set_traits : simple_hashmap_traits <alias_set_hash> {};
 
 struct GTY(()) alias_set_entry_d {
   /* The alias set number, as stored in MEM_ALIAS_SET.  */
Index: gcc/symbol-summary.h
===================================================================
--- gcc/symbol-summary.h	2015-06-23 15:50:56.686110247 +0100
+++ gcc/symbol-summary.h	2015-06-23 15:50:56.678110339 +0100
@@ -200,45 +200,8 @@ class GTY((user)) function_summary <T *>
   bool m_ggc;
 
 private:
-  struct summary_hashmap_traits: default_hashmap_traits
-  {
-    static const int deleted_value = -1;
-    static const int empty_value = 0;
-
-    static hashval_t
-    hash (const int v)
-    {
-      return (hashval_t)v;
-    }
-
-    template<typename Type>
-    static bool
-    is_deleted (Type &e)
-    {
-      return e.m_key == deleted_value;
-    }
-
-    template<typename Type>
-    static bool
-    is_empty (Type &e)
-    {
-      return e.m_key == empty_value;
-    }
-
-    template<typename Type>
-    static void
-    mark_deleted (Type &e)
-    {
-      e.m_key = deleted_value;
-    }
-
-    template<typename Type>
-    static void
-    mark_empty (Type &e)
-    {
-      e.m_key = empty_value;
-    }
-  };
+  typedef int_hash <int, 0, -1> map_hash;
+  typedef simple_hashmap_traits <map_hash> summary_hashmap_traits;
 
   /* Getter for summary callgraph ID.  */
   T* get (int uid)
Index: gcc/tree-inline.h
===================================================================
--- gcc/tree-inline.h	2015-06-23 15:50:56.686110247 +0100
+++ gcc/tree-inline.h	2015-06-23 15:50:56.678110339 +0100
@@ -35,25 +35,8 @@ enum copy_body_cge_which
   CB_CGE_MOVE_CLONES
 };
 
-struct dependence_hasher : default_hashmap_traits
-{
-  template<typename T>
-  static void
-  mark_deleted (T &e)
-    { gcc_unreachable (); }
-
-  template<typename T>
-  static void
-  mark_empty (T &e)
-    { e.m_key = 0; }
-
-  template<typename T>
-  static bool
-  is_deleted (T &)
-    { return false; }
-
-  template<typename T> static bool is_empty (T &e) { return e.m_key == 0; }
-};
+typedef int_hash <unsigned short, 0> dependence_hash;
+typedef simple_hashmap_traits <dependence_hash> dependence_hasher;
 
 /* Data required for function body duplication.  */
 
Index: gcc/tree-ssa-reassoc.c
===================================================================
--- gcc/tree-ssa-reassoc.c	2015-06-23 15:50:56.686110247 +0100
+++ gcc/tree-ssa-reassoc.c	2015-06-23 15:50:56.678110339 +0100
@@ -1019,23 +1019,16 @@ typedef struct oecount_s {
 
 /* Oecount hashtable helpers.  */
 
-struct oecount_hasher
+struct oecount_hasher : int_hash <int, 0, 1>
 {
-  typedef int value_type;
-  typedef int compare_type;
-  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 &) {}
+  static inline hashval_t hash (int);
+  static inline bool equal (int, int);
 };
 
 /* Hash function for oecount.  */
 
 inline hashval_t
-oecount_hasher::hash (const value_type &p)
+oecount_hasher::hash (int p)
 {
   const oecount *c = &cvec[p - 42];
   return htab_hash_pointer (c->op) ^ (hashval_t)c->oecode;
@@ -1044,7 +1037,7 @@ oecount_hasher::hash (const value_type &
 /* Comparison function for oecount.  */
 
 inline bool
-oecount_hasher::equal (const value_type &p1, const compare_type &p2)
+oecount_hasher::equal (int p1, int p2)
 {
   const oecount *c1 = &cvec[p1 - 42];
   const oecount *c2 = &cvec[p2 - 42];
Index: gcc/value-prof.c
===================================================================
--- gcc/value-prof.c	2015-06-23 15:50:56.686110247 +0100
+++ gcc/value-prof.c	2015-06-23 15:50:56.682110292 +0100
@@ -1250,19 +1250,8 @@ gimple_mod_subtract_transform (gimple_st
   return true;
 }
 
-struct profile_id_traits : default_hashmap_traits
-{
-  template<typename T>
-  static bool
-  is_deleted (T &e)
-    {
-      return e.m_key == UINT_MAX;
-    }
-
-  template<typename T> static bool is_empty (T &e) { return e.m_key == 0; }
-  template<typename T> static void mark_deleted (T &e) { e.m_key = UINT_MAX; }
-  template<typename T> static void mark_empty (T &e) { e.m_key = 0; }
-};
+typedef int_hash <unsigned int, 0, UINT_MAX> profile_id_hash;
+typedef simple_hashmap_traits <profile_id_hash> profile_id_traits;
 
 static hash_map<unsigned int, cgraph_node *, profile_id_traits> *
 cgraph_node_map = 0;