add hash_map class

gcc/

	* alloc-pool.c (alloc_pool_hash): Use hash_map instead of hash_table.
	* dominance.c (iterate_fix_dominators): Use hash_map instead of
	pointer_map.
	* hash-map.h: New file.
	* ipa-comdats.c: Use hash_map instead of pointer_map.
	* ipa.c: Likewise.
	* lto-section-out.c: Adjust.
	* lto-streamer.h: Replace pointer_map with hash_map.
	* symtab.c (verify_symtab): Likewise.
	* tree-ssa-strlen.c (decl_to_stridxlist_htab): Likewise.
	* tree-ssa-uncprop.c (val_ssa_equiv): Likewise.
	* tree-streamer.h: Likewise.
	* tree-streamer.c: Adjust.
	* pointer-set.h: Remove pointer_map.

gcc/lto/

	* lto.c (canonical_type_hash_cache): Use hash_map instead of
	pointer_map.

git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@211938 138bc75d-0d04-0410-961f-82ee72b054a4

16 files changed, 325 insertions, 308 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index bf1a716e751..fe5d2ffcac9 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,5 +1,22 @@
 2014-06-24  Trevor Saunders  <tsaunders@mozilla.com>
 
+	* alloc-pool.c (alloc_pool_hash): Use hash_map instead of hash_table.
+	* dominance.c (iterate_fix_dominators): Use hash_map instead of
+	pointer_map.
+	* hash-map.h: New file.
+	* ipa-comdats.c: Use hash_map instead of pointer_map.
+	* ipa.c: Likewise.
+	* lto-section-out.c: Adjust.
+	* lto-streamer.h: Replace pointer_map with hash_map.
+	* symtab.c (verify_symtab): Likewise.
+	* tree-ssa-strlen.c (decl_to_stridxlist_htab): Likewise.
+	* tree-ssa-uncprop.c (val_ssa_equiv): Likewise.
+	* tree-streamer.h: Likewise.
+	* tree-streamer.c: Adjust.
+	* pointer-set.h: Remove pointer_map.
+
+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.
diff --git a/gcc/alloc-pool.c b/gcc/alloc-pool.c
index 49209ee6845..0d318351474 100644
--- a/gcc/alloc-pool.c
+++ b/gcc/alloc-pool.c
@@ -22,6 +22,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "system.h"
 #include "alloc-pool.h"
 #include "hash-table.h"
+#include "hash-map.h"
 
 #define align_eight(x) (((x+7) >> 3) << 3)
 
@@ -69,7 +70,6 @@ static ALLOC_POOL_ID_TYPE last_id;
    size for that pool.  */
 struct alloc_pool_descriptor
 {
-  const char *name;
   /* Number of pools allocated.  */
   unsigned long created;
   /* Gross allocated storage.  */
@@ -82,48 +82,17 @@ struct alloc_pool_descriptor
   int elt_size;
 };
 
-/* Hashtable helpers.  */
-struct alloc_pool_hasher : typed_noop_remove <alloc_pool_descriptor>
-{
-  typedef alloc_pool_descriptor value_type;
-  typedef char compare_type;
-  static inline hashval_t hash (const alloc_pool_descriptor *);
-  static inline bool equal (const value_type *, const compare_type *);
-};
-
-inline hashval_t
-alloc_pool_hasher::hash (const value_type *d)
-{
-  return htab_hash_pointer (d->name);
-}
-
-inline bool
-alloc_pool_hasher::equal (const value_type *d,
-                          const compare_type *p2)
-{
-  return d->name == p2;
-}
-
 /* Hashtable mapping alloc_pool names to descriptors.  */
-static hash_table<alloc_pool_hasher> *alloc_pool_hash;
+static hash_map<const char *, alloc_pool_descriptor> *alloc_pool_hash;
 
 /* For given name, return descriptor, create new if needed.  */
 static struct alloc_pool_descriptor *
 allocate_pool_descriptor (const char *name)
 {
-  struct alloc_pool_descriptor **slot;
-
   if (!alloc_pool_hash)
-    alloc_pool_hash = new hash_table<alloc_pool_hasher> (10);
-
-  slot = alloc_pool_hash->find_slot_with_hash (name,
-					       htab_hash_pointer (name),
-					       INSERT);
-  if (*slot)
-    return *slot;
-  *slot = XCNEW (struct alloc_pool_descriptor);
-  (*slot)->name = name;
-  return *slot;
+    alloc_pool_hash = new hash_map<const char *, alloc_pool_descriptor> (10);
+
+  return &alloc_pool_hash->get_or_insert (name);
 }
 
 /* Create a pool of things of size SIZE, with NUM in each block we
@@ -375,23 +344,22 @@ struct output_info
   unsigned long total_allocated;
 };
 
-/* Called via hash_table.traverse.  Output alloc_pool descriptor pointed out by
+/* Called via hash_map.traverse.  Output alloc_pool descriptor pointed out by
    SLOT and update statistics.  */
-int
-print_alloc_pool_statistics (alloc_pool_descriptor **slot,
+bool
+print_alloc_pool_statistics (const char *const &name,
+			     const alloc_pool_descriptor &d,
 			     struct output_info *i)
 {
-  struct alloc_pool_descriptor *d = *slot;
-
-  if (d->allocated)
+  if (d.allocated)
     {
       fprintf (stderr,
 	       "%-22s %6d %10lu %10lu(%10lu) %10lu(%10lu) %10lu(%10lu)\n",
-	       d->name, d->elt_size, d->created, d->allocated,
-	       d->allocated / d->elt_size, d->peak, d->peak / d->elt_size,
-	       d->current, d->current / d->elt_size);
-      i->total_allocated += d->allocated;
-      i->total_created += d->created;
+	       name, d.elt_size, d.created, d.allocated,
+	       d.allocated / d.elt_size, d.peak, d.peak / d.elt_size,
+	       d.current, d.current / d.elt_size);
+      i->total_allocated += d.allocated;
+      i->total_created += d.created;
     }
   return 1;
 }
diff --git a/gcc/dominance.c b/gcc/dominance.c
index 7adec4f7376..be0a43910e6 100644
--- a/gcc/dominance.c
+++ b/gcc/dominance.c
@@ -43,6 +43,7 @@
 #include "diagnostic-core.h"
 #include "et-forest.h"
 #include "timevar.h"
+#include "hash-map.h"
 #include "pointer-set.h"
 #include "graphds.h"
 #include "bitmap.h"
@@ -1258,7 +1259,6 @@ iterate_fix_dominators (enum cdi_direction dir, vec<basic_block> bbs,
   size_t dom_i;
   edge e;
   edge_iterator ei;
-  pointer_map<int> *map;
   int *parent, *son, *brother;
   unsigned int dir_index = dom_convert_dir_to_idx (dir);
 
@@ -1346,15 +1346,15 @@ iterate_fix_dominators (enum cdi_direction dir, vec<basic_block> bbs,
     }
 
   /* Construct the graph G.  */
-  map = new pointer_map<int>;
+  hash_map<basic_block, int> map (251);
   FOR_EACH_VEC_ELT (bbs, i, bb)
     {
       /* If the dominance tree is conservatively correct, split it now.  */
       if (conservative)
 	set_immediate_dominator (CDI_DOMINATORS, bb, NULL);
-      *map->insert (bb) = i;
+      map.put (bb, i);
     }
-  *map->insert (ENTRY_BLOCK_PTR_FOR_FN (cfun)) = n;
+  map.put (ENTRY_BLOCK_PTR_FOR_FN (cfun), n);
 
   g = new_graph (n + 1);
   for (y = 0; y < g->n_vertices; y++)
@@ -1367,7 +1367,7 @@ iterate_fix_dominators (enum cdi_direction dir, vec<basic_block> bbs,
 	  if (dom == bb)
 	    continue;
 
-	  dom_i = *map->contains (dom);
+	  dom_i = *map.get (dom);
 
 	  /* Do not include parallel edges to G.  */
 	  if (!bitmap_set_bit ((bitmap) g->vertices[dom_i].data, i))
@@ -1378,7 +1378,6 @@ iterate_fix_dominators (enum cdi_direction dir, vec<basic_block> bbs,
     }
   for (y = 0; y < g->n_vertices; y++)
     BITMAP_FREE (g->vertices[y].data);
-  delete map;
 
   /* Find the dominator tree of G.  */
   son = XNEWVEC (int, n + 1);
diff --git a/gcc/hash-map.h b/gcc/hash-map.h
new file mode 100644
index 00000000000..0b50f724251
--- /dev/null
+++ b/gcc/hash-map.h
@@ -0,0 +1,203 @@
+/* A type-safe hash map.
+   Copyright (C) 2014 Free Software Foundation, Inc.
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify it under
+the terms of the GNU General Public License as published by the Free
+Software Foundation; either version 3, or (at your option) any later
+version.
+
+GCC is distributed in the hope that it will be useful, but WITHOUT ANY
+WARRANTY; without even the implied warranty of MERCHANTABILITY or
+FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING3.  If not see
+<http://www.gnu.org/licenses/>.  */
+
+
+#ifndef hash_map_h
+#define hash_map_h
+
+#include "hash-table.h"
+
+/* implement default behavior for traits when types allow it.  */
+
+struct default_hashmap_traits
+{
+  /* Hashes the passed in key.  */
+
+  template<typename T>
+  static hashval_t
+  hash (T *p)
+    {
+      return uintptr_t(p) >> 3;
+    }
+
+  /* The right thing to do here would be using is_integral to only allow
+     template arguments of integer type, but reimplementing that is a pain, so
+     we'll just promote everything to [u]int64_t and truncate to hashval_t.  */
+
+  static hashval_t hash (uint64_t v) { return v; }
+  static hashval_t hash (int64_t v) { return v; }
+
+  /* Return true if the two keys passed as arguments are equal.  */
+
+  template<typename T>
+  static bool
+  equal_keys (const T &a, const T &b)
+    {
+      return a == b;
+    }
+
+  /* Called to dispose of the key and value before marking the entry as
+     deleted.  */
+
+  template<typename T> static void remove (T &v) { v.~T (); }
+
+  /* Mark the passed in entry as being deleted.  */
+
+  template<typename T>
+  static void
+  mark_deleted (T &e)
+    {
+      mark_key_deleted (e.m_key);
+    }
+
+  /* Mark the passed in entry as being empty.  */
+
+  template<typename T>
+  static void
+  mark_empty (T &e)
+    {
+      mark_key_empty (e.m_key);
+    }
+
+  /* Return true if the passed in entry is marked as deleted.  */
+
+  template<typename T>
+  static bool
+  is_deleted (T &e)
+    {
+      return e.m_key == (void *)1;
+    }
+
+  /* Return true if the passed in entry is marked as empty.  */
+
+  template<typename T> static bool is_empty (T &e) { return e.m_key == NULL; }
+
+private:
+  template<typename T>
+  static void
+  mark_key_deleted (T *&k)
+    {
+      k = static_cast<T *> (1);
+    }
+
+  template<typename T>
+  static void
+  mark_key_empty (T *&k)
+    {
+      k = static_cast<T *> (0);
+    }
+};
+
+template<typename Key, typename Value,
+	 typename Traits = default_hashmap_traits>
+class hash_map
+{
+  struct hash_entry
+  {
+    Key m_key;
+    Value m_value;
+
+    typedef hash_entry value_type;
+    typedef Key compare_type;
+    typedef int store_values_directly;
+
+    static hashval_t hash (const hash_entry &e)
+      {
+       	return Traits::hash (e.m_key);
+      }
+
+    static bool equal (const hash_entry &a, const Key &b)
+       	{
+	  return Traits::equal_keys (a.m_key, b);
+       	}
+
+    static void remove (hash_entry &e) { Traits::remove (e); }
+
+    static void mark_deleted (hash_entry &e) { Traits::mark_deleted (e); }
+
+    static bool is_deleted (const hash_entry &e)
+      {
+       	return Traits::is_deleted (e);
+      }
+
+    static void mark_empty (hash_entry &e) { Traits::mark_empty (e); }
+    static bool is_empty (const hash_entry &e) { return Traits::is_empty (e); }
+  };
+
+public:
+  explicit hash_map (size_t n = 13) : m_table (n) {}
+
+  /* If key k isn't already in the map add key k with value v to the map, and
+     return false.  Otherwise set the value of the entry for key k to be v and
+     return true.  */
+
+  bool put (const Key &k, const Value &v)
+    {
+      hash_entry *e = m_table.find_slot_with_hash (k, Traits::hash (k),
+						   INSERT);
+      bool existed = !hash_entry::is_empty (*e);
+      if (!existed)
+	e->m_key = k;
+
+      e->m_value = v;
+      return existed;
+    }
+
+  /* if the passed in key is in the map return its value otherwise NULL.  */
+
+  Value *get (const Key &k)
+    {
+      hash_entry &e = m_table.find_with_hash (k, Traits::hash (k));
+      return Traits::is_empty (e) ? NULL : &e.m_value;
+    }
+
+  /* Return a reference to the value for the passed in key, creating the entry
+     if it doesn't already exist.  If existed is not NULL then it is set to false
+     if the key was not previously in the map, and true otherwise.  */
+
+  Value &get_or_insert (const Key &k, bool *existed = NULL)
+    {
+      hash_entry *e = m_table.find_slot_with_hash (k, Traits::hash (k),
+						   INSERT);
+      bool ins = Traits::is_empty (*e);
+      if (ins)
+	e->m_key = k;
+
+      if (existed != NULL)
+	*existed = !ins;
+
+      return e->m_value;
+    }
+
+  /* Call the call back on each pair of key and value with the passed in
+     arg.  */
+
+  template<typename Arg, bool (*f)(const Key &, const Value &, Arg)>
+  void traverse (Arg a) const
+    {
+      for (typename hash_table<hash_entry>::iterator iter = m_table.begin ();
+	   iter != m_table.end (); ++iter)
+	f ((*iter).m_key, (*iter).m_value, a);
+    }
+
+private:
+  hash_table<hash_entry> m_table;
+};
+
+#endif
diff --git a/gcc/ipa-comdats.c b/gcc/ipa-comdats.c
index 69269009ac7..b1bc35e9392 100644
--- a/gcc/ipa-comdats.c
+++ b/gcc/ipa-comdats.c
@@ -55,7 +55,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "tree.h"
 #include "cgraph.h"
 #include "tree-pass.h"
-#include "pointer-set.h"
+#include "hash-map.h"
 
 /* Main dataflow loop propagating comdat groups across
    the symbol table.  All references to SYMBOL are examined
@@ -64,7 +64,7 @@ along with GCC; see the file COPYING3.  If not see
 
 tree
 propagate_comdat_group (struct symtab_node *symbol,
-			tree newgroup, pointer_map <tree> &map)
+			tree newgroup, hash_map<symtab_node *, tree> &map)
 {
   int i;
   struct ipa_ref *ref;
@@ -105,7 +105,7 @@ propagate_comdat_group (struct symtab_node *symbol,
 
       /* The actual merge operation.  */
 
-      tree *val2 = map.contains (symbol2);
+      tree *val2 = map.get (symbol2);
 
       if (val2 && *val2 != newgroup)
 	{
@@ -138,7 +138,7 @@ propagate_comdat_group (struct symtab_node *symbol,
 
         /* The actual merge operation.  */
 
-	tree *val2 = map.contains (symbol2);
+	tree *val2 = map.get (symbol2);
 
 	if (val2 && *val2 != newgroup)
 	  {
@@ -213,8 +213,8 @@ set_comdat_group (symtab_node *symbol,
 static unsigned int
 ipa_comdats (void)
 {
-  pointer_map<tree> map;
-  pointer_map<symtab_node *> comdat_head_map;
+  hash_map<symtab_node *, tree> map (251);
+  hash_map<tree, symtab_node *> comdat_head_map (251);
   symtab_node *symbol;
   bool comdat_group_seen = false;
   symtab_node *first = (symtab_node *) (void *) 1;
@@ -229,8 +229,8 @@ ipa_comdats (void)
       ;
     else if ((group = symbol->get_comdat_group ()) != NULL)
       {
-        *map.insert (symbol) = group;
-        *comdat_head_map.insert (group) = symbol;
+        map.put (symbol, group);
+        comdat_head_map.put (group, symbol);
 	comdat_group_seen = true;
 
 	/* Mark the symbol so we won't waste time visiting it for dataflow.  */
@@ -248,7 +248,7 @@ ipa_comdats (void)
 		 && (DECL_STATIC_CONSTRUCTOR (symbol->decl)
 		     || DECL_STATIC_DESTRUCTOR (symbol->decl))))
       {
-	*map.insert (symtab_alias_ultimate_target (symbol, NULL)) = error_mark_node;
+	map.put (symtab_alias_ultimate_target (symbol, NULL), error_mark_node);
 
 	/* Mark the symbol so we won't waste time visiting it for dataflow.  */
 	symbol->aux = (symtab_node *) (void *) 1;
@@ -278,7 +278,7 @@ ipa_comdats (void)
       first = (symtab_node *)first->aux;
 
       /* Get current lattice value of SYMBOL.  */
-      val = map.contains (symbol);
+      val = map.get (symbol);
       if (val)
 	group = *val;
 
@@ -301,7 +301,7 @@ ipa_comdats (void)
       if (val)
 	*val = newgroup;
       else
-	*map.insert (symbol) = newgroup;
+	map.put (symbol, newgroup);
       enqueue_references (&first, symbol);
 
       /* We may need to revisit the symbol unless it is BOTTOM.  */
@@ -318,7 +318,7 @@ ipa_comdats (void)
 	  && !symbol->alias
 	  && symtab_real_symbol_p (symbol))
 	{
-	  tree group = *map.contains (symbol);
+	  tree group = *map.get (symbol);
 
 	  if (group == error_mark_node)
 	    continue;
@@ -329,7 +329,7 @@ ipa_comdats (void)
 	      fprintf (dump_file, "To group: %s\n", IDENTIFIER_POINTER (group));
 	    }
 	  symtab_for_node_and_aliases (symbol, set_comdat_group,
-				       *comdat_head_map.contains (group), true);
+				       *comdat_head_map.get (group), true);
 	}
     }
   return 0;
diff --git a/gcc/ipa.c b/gcc/ipa.c
index 33bf5104530..04f2c79ae33 100644
--- a/gcc/ipa.c
+++ b/gcc/ipa.c
@@ -26,6 +26,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "stringpool.h"
 #include "cgraph.h"
 #include "tree-pass.h"
+#include "hash-map.h"
 #include "pointer-set.h"
 #include "gimple-expr.h"
 #include "gimplify.h"
@@ -1113,14 +1114,14 @@ make_pass_ipa_cdtor_merge (gcc::context *ctxt)
 
 cgraph_node *
 meet (cgraph_node *function, varpool_node *var,
-       pointer_map<cgraph_node *> &single_user_map)
+       hash_map<varpool_node *, cgraph_node *> &single_user_map)
 {
   struct cgraph_node *user, **f;
 
   if (var->aux == BOTTOM)
     return BOTTOM;
 
-  f = single_user_map.contains (var);
+  f = single_user_map.get (var);
   if (!f)
     return function;
   user = *f;
@@ -1139,7 +1140,7 @@ meet (cgraph_node *function, varpool_node *var,
 
 cgraph_node *
 propagate_single_user (varpool_node *vnode, cgraph_node *function,
-		       pointer_map<cgraph_node *> &single_user_map)
+		       hash_map<varpool_node *, cgraph_node *> &single_user_map)
 {
   int i;
   struct ipa_ref *ref;
@@ -1180,7 +1181,7 @@ ipa_single_use (void)
 {
   varpool_node *first = (varpool_node *) (void *) 1;
   varpool_node *var;
-  pointer_map<cgraph_node *> single_user_map;
+  hash_map<varpool_node *, cgraph_node *> single_user_map;
 
   FOR_EACH_DEFINED_VARIABLE (var)
     if (!varpool_all_refs_explicit_p (var))
@@ -1201,7 +1202,7 @@ ipa_single_use (void)
       var = first;
       first = (varpool_node *)first->aux;
 
-      f = single_user_map.contains (var);
+      f = single_user_map.get (var);
       if (f)
 	orig_user = *f;
       else
@@ -1216,7 +1217,7 @@ ipa_single_use (void)
 	  unsigned int i;
 	  ipa_ref *ref;
 
-	  *single_user_map.insert (var) = user;
+	  single_user_map.put (var, user);
 
 	  /* Enqueue all aliases for re-processing.  */
 	  for (i = 0;
@@ -1253,8 +1254,8 @@ ipa_single_use (void)
       if (var->aux != BOTTOM)
 	{
 #ifdef ENABLE_CHECKING
-	  if (!single_user_map.contains (var))
-          gcc_assert (single_user_map.contains (var));
+	  if (!single_user_map.get (var))
+          gcc_assert (single_user_map.get (var));
 #endif
 	  if (dump_file)
 	    {
diff --git a/gcc/lto-section-out.c b/gcc/lto-section-out.c
index 9d6926c57cf..00b18016a83 100644
--- a/gcc/lto-section-out.c
+++ b/gcc/lto-section-out.c
@@ -224,21 +224,17 @@ lto_output_decl_index (struct lto_output_stream *obs,
 		       struct lto_tree_ref_encoder *encoder,
 		       tree name, unsigned int *this_index)
 {
-  unsigned *slot;
-  unsigned int index;
   bool new_entry_p = FALSE;
   bool existed_p;
 
-  slot = encoder->tree_hash_table->insert (name, &existed_p);
+  unsigned int &index
+    = encoder->tree_hash_table->get_or_insert (name, &existed_p);
   if (!existed_p)
     {
       index = encoder->trees.length ();
-      *slot = index;
       encoder->trees.safe_push (name);
       new_entry_p = TRUE;
     }
-  else
-    index = *slot;
 
   if (obs)
     streamer_write_uhwi_stream (obs, index);
diff --git a/gcc/lto-streamer.h b/gcc/lto-streamer.h
index 889e91dbc25..566a0e0b359 100644
--- a/gcc/lto-streamer.h
+++ b/gcc/lto-streamer.h
@@ -25,6 +25,7 @@ along with GCC; see the file COPYING3.  If not see
 
 #include "plugin-api.h"
 #include "hash-table.h"
+#include "hash-map.h"
 #include "target.h"
 #include "cgraph.h"
 #include "vec.h"
@@ -472,7 +473,7 @@ struct GTY(()) lto_tree_ref_table
 
 struct lto_tree_ref_encoder
 {
-  pointer_map<unsigned> *tree_hash_table;	/* Maps pointers to indices. */
+  hash_map<tree, unsigned> *tree_hash_table;	/* Maps pointers to indices. */
   vec<tree> trees;			/* Maps indices to pointers. */
 };
 
@@ -994,7 +995,7 @@ lto_tag_check_range (enum LTO_tags actual, enum LTO_tags tag1,
 static inline void
 lto_init_tree_ref_encoder (struct lto_tree_ref_encoder *encoder)
 {
-  encoder->tree_hash_table = new pointer_map<unsigned>;
+  encoder->tree_hash_table = new hash_map<tree, unsigned> (251);
   encoder->trees.create (0);
 }
 
@@ -1005,8 +1006,8 @@ static inline void
 lto_destroy_tree_ref_encoder (struct lto_tree_ref_encoder *encoder)
 {
   /* Hash table may be delete already.  */
-  if (encoder->tree_hash_table)
-    delete encoder->tree_hash_table;
+  delete encoder->tree_hash_table;
+  encoder->tree_hash_table = NULL;
   encoder->trees.release ();
 }
 
diff --git a/gcc/lto/ChangeLog b/gcc/lto/ChangeLog
index 29d7a5bff71..83a684e07a5 100644
--- a/gcc/lto/ChangeLog
+++ b/gcc/lto/ChangeLog
@@ -1,5 +1,10 @@
 2014-06-24  Trevor Saunders  <tsaunders@mozilla.com>
 
+	* lto.c (canonical_type_hash_cache): Use hash_map instead of
+	pointer_map.
+
+2014-06-24  Trevor Saunders  <tsaunders@mozilla.com>
+
 	* lto.c: Adjust.
 
 2014-06-20  Jan Hubicka  <hubicka@ucw.cz>
diff --git a/gcc/lto/lto.c b/gcc/lto/lto.c
index 1fe7ce4eefb..5c4acc5e469 100644
--- a/gcc/lto/lto.c
+++ b/gcc/lto/lto.c
@@ -32,6 +32,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "tree-pass.h"
 #include "langhooks.h"
 #include "bitmap.h"
+#include "hash-map.h"
 #include "ipa-prop.h"
 #include "common.h"
 #include "debug.h"
@@ -261,7 +262,7 @@ lto_read_in_decl_state (struct data_in *data_in, const uint32_t *data,
 
 /* Global canonical type table.  */
 static htab_t gimple_canonical_types;
-static pointer_map <hashval_t> *canonical_type_hash_cache;
+static hash_map<const_tree, hashval_t> *canonical_type_hash_cache;
 static unsigned long num_canonical_type_hash_entries;
 static unsigned long num_canonical_type_hash_queries;
 
@@ -405,8 +406,7 @@ static hashval_t
 gimple_canonical_type_hash (const void *p)
 {
   num_canonical_type_hash_queries++;
-  hashval_t *slot
-    = canonical_type_hash_cache->contains (CONST_CAST_TREE ((const_tree) p));
+  hashval_t *slot = canonical_type_hash_cache->get ((const_tree) p);
   gcc_assert (slot != NULL);
   return *slot;
 }
@@ -648,10 +648,8 @@ gimple_register_canonical_type_1 (tree t, hashval_t hash)
       *slot = (void *) t;
       /* Cache the just computed hash value.  */
       num_canonical_type_hash_entries++;
-      bool existed_p;
-      hashval_t *hslot = canonical_type_hash_cache->insert (t, &existed_p);
+      bool existed_p = canonical_type_hash_cache->put (t, hash);
       gcc_assert (!existed_p);
-      *hslot = hash;
     }
 }
 
@@ -2917,7 +2915,7 @@ read_cgraph_and_symbols (unsigned nfiles, const char **fnames)
     }
   cgraph_state = CGRAPH_LTO_STREAMING;
 
-  canonical_type_hash_cache = new pointer_map <hashval_t>;
+  canonical_type_hash_cache = new hash_map<const_tree, hashval_t> (251);
   gimple_canonical_types = htab_create_ggc (16381, gimple_canonical_type_hash,
 					    gimple_canonical_type_eq, 0);
   gcc_obstack_init (&tree_scc_hash_obstack);
diff --git a/gcc/pointer-set.h b/gcc/pointer-set.h
index a426534ac44..fc592121872 100644
--- a/gcc/pointer-set.h
+++ b/gcc/pointer-set.h
@@ -45,117 +45,6 @@ void pointer_set_traverse (const struct pointer_set_t *,
 			   void *);
 bool pointer_set_lookup (const pointer_set_t *, const void *, size_t *);
 
-/* A pointer map is represented the same way as a pointer_set, so
-   the hash code is based on the address of the key, rather than
-   its contents.  Null keys are a reserved value.  Deletion is not
-   supported (yet).  There is no mechanism for user control of hash
-   function, equality comparison, initial size, or resizing policy.  */
-
-template <typename T>
-class pointer_map : protected pointer_set_t
-{
-  T *values;
-
-public:
-  pointer_map ();
-  ~pointer_map ();
-  T *contains (const void *p);
-  T *insert (const void *p, bool *existed_p = NULL);
-  void traverse (bool (*fn) (const void *, T *, void *), void *data);
-};
-
-/* Allocate an empty pointer map.  */
-template <typename T>
-pointer_map<T>::pointer_map (void)
-{
-  n_elements = 0;
-  log_slots = 8;
-  n_slots = (size_t) 1 << log_slots;
-
-  slots = XCNEWVEC (const void *, n_slots);
-  values = XNEWVEC (T, n_slots);
-}
-
-/* Reclaims all memory associated with PMAP.  */
-template <typename T>
-pointer_map<T>::~pointer_map (void)
-{
-  XDELETEVEC (slots);
-  XDELETEVEC (values);
-}
-
-/* Returns a pointer to the value to which P maps, if PMAP contains P.  P
-   must be nonnull.  Return NULL if PMAP does not contain P.
-
-   Collisions are resolved by linear probing.  */
-template <typename T>
-T *
-pointer_map<T>::contains (const void *p)
-{
-  size_t n;
-  if (!pointer_set_lookup (this, p, &n))
-    return NULL;
-  return &values[n];
-}
-
-/* Inserts P into PMAP if it wasn't already there.  Returns a pointer
-   to the value.  P must be nonnull.  */
-template <typename T>
-T *
-pointer_map<T>::insert (const void *p, bool *existed_p)
-{
-  size_t n;
-
-  /* For simplicity, expand the map even if P is already there.  This can be
-     superfluous but can happen at most once.  */
-  /* ???  Fugly that we have to inline that here.  */
-  if (n_elements > n_slots / 4)
-    {
-      size_t old_n_slots = n_slots;
-      const void **old_keys = slots;
-      T *old_values = values;
-      log_slots = log_slots + 1;
-      n_slots = n_slots * 2;
-      slots = XCNEWVEC (const void *, n_slots);
-      values = XNEWVEC (T, n_slots);
-      for (size_t i = 0; i < old_n_slots; ++i)
-	if (old_keys[i])
-	  {
-	    const void *key = old_keys[i];
-	    pointer_set_lookup (this, key, &n);
-	    slots[n] = key;
-	    values[n] = old_values[i];
-	  }
-      XDELETEVEC (old_keys);
-      XDELETEVEC (old_values);
-    }
-
-  if (!pointer_set_lookup (this, p, &n))
-    {
-      ++n_elements;
-      slots[n] = p;
-      if (existed_p)
-	*existed_p = false;
-    }
-  else if (existed_p)
-    *existed_p = true;
-
-  return &values[n];
-}
-
-/* Pass each pointer in PMAP to the function in FN, together with the pointer
-   to the value and the fixed parameter DATA.  If FN returns false, the
-   iteration stops.  */
-
-template <class T>
-void
-pointer_map<T>::traverse (bool (*fn) (const void *, T *, void *), void *data)
-{
-  for (size_t i = 0; i < n_slots; ++i)
-    if (slots[i] && !fn (slots[i], &values[i], data))
-      break;
-}
-
 
 struct pointer_map_t;
 pointer_map_t *pointer_map_create (void);
diff --git a/gcc/symtab.c b/gcc/symtab.c
index 13895657856..6e521154fa8 100644
--- a/gcc/symtab.c
+++ b/gcc/symtab.c
@@ -895,7 +895,7 @@ DEBUG_FUNCTION void
 verify_symtab (void)
 {
   symtab_node *node;
-  pointer_map<symtab_node *> comdat_head_map;
+  hash_map<tree, symtab_node *> comdat_head_map (251);
 
   FOR_EACH_SYMBOL (node)
     {
@@ -905,7 +905,8 @@ verify_symtab (void)
 	  symtab_node **entry, *s;
 	  bool existed;
 
-	  entry = comdat_head_map.insert (node->get_comdat_group (), &existed);
+	  entry = &comdat_head_map.get_or_insert (node->get_comdat_group (),
+						  &existed);
 	  if (!existed)
 	    *entry = node;
 	  else
diff --git a/gcc/tree-ssa-strlen.c b/gcc/tree-ssa-strlen.c
index b452d9d6d4c..dc659c93dd5 100644
--- a/gcc/tree-ssa-strlen.c
+++ b/gcc/tree-ssa-strlen.c
@@ -24,6 +24,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "tree.h"
 #include "stor-layout.h"
 #include "hash-table.h"
+#include "hash-map.h"
 #include "bitmap.h"
 #include "basic-block.h"
 #include "tree-ssa-alias.h"
@@ -134,31 +135,23 @@ struct decl_stridxlist_map
 
 /* stridxlist hashtable helpers.  */
 
-struct stridxlist_hasher : typed_noop_remove <decl_stridxlist_map>
+struct stridxlist_hash_traits : default_hashmap_traits
 {
-  typedef decl_stridxlist_map value_type;
-  typedef decl_stridxlist_map compare_type;
-  static inline hashval_t hash (const value_type *);
-  static inline bool equal (const value_type *, const compare_type *);
+  static inline hashval_t hash (tree);
 };
 
 /* Hash a from tree in a decl_stridxlist_map.  */
 
 inline hashval_t
-stridxlist_hasher::hash (const value_type *item)
+stridxlist_hash_traits::hash (tree item)
 {
-  return DECL_UID (item->base.from);
-}
-
-inline bool
-stridxlist_hasher::equal (const value_type *v, const compare_type *c)
-{
-  return tree_map_base_eq (&v->base, &c->base);
+  return DECL_UID (item);
 }
 
 /* Hash table for mapping decls to a chained list of offset -> idx
    mappings.  */
-static hash_table<stridxlist_hasher> *decl_to_stridxlist_htab;
+static hash_map<tree, stridxlist, stridxlist_hash_traits>
+  *decl_to_stridxlist_htab;
 
 /* Obstack for struct stridxlist and struct decl_stridxlist_map.  */
 static struct obstack stridx_obstack;
@@ -179,7 +172,6 @@ static int
 get_addr_stridx (tree exp)
 {
   HOST_WIDE_INT off;
-  struct decl_stridxlist_map ent, *e;
   struct stridxlist *list;
   tree base;
 
@@ -190,12 +182,10 @@ get_addr_stridx (tree exp)
   if (base == NULL || !DECL_P (base))
     return 0;
 
-  ent.base.from = base;
-  e = decl_to_stridxlist_htab->find_with_hash (&ent, DECL_UID (base));
-  if (e == NULL)
+  list = decl_to_stridxlist_htab->get (base);
+  if (list == NULL)
     return 0;
 
-  list = &e->list;
   do
     {
       if (list->offset == off)
@@ -270,9 +260,6 @@ unshare_strinfo_vec (void)
 static int *
 addr_stridxptr (tree exp)
 {
-  decl_stridxlist_map **slot;
-  struct decl_stridxlist_map ent;
-  struct stridxlist *list;
   HOST_WIDE_INT off;
 
   tree base = get_addr_base_and_unit_offset (exp, &off);
@@ -281,16 +268,16 @@ addr_stridxptr (tree exp)
 
   if (!decl_to_stridxlist_htab)
     {
-      decl_to_stridxlist_htab = new hash_table<stridxlist_hasher> (64);
+      decl_to_stridxlist_htab
+       	= new hash_map<tree, stridxlist, stridxlist_hash_traits> (64);
       gcc_obstack_init (&stridx_obstack);
     }
-  ent.base.from = base;
-  slot = decl_to_stridxlist_htab->find_slot_with_hash (&ent, DECL_UID (base),
-						       INSERT);
-  if (*slot)
+
+  bool existed;
+  stridxlist *list = &decl_to_stridxlist_htab->get_or_insert (base, &existed);
+  if (existed)
     {
       int i;
-      list = &(*slot)->list;
       for (i = 0; i < 16; i++)
 	{
 	  if (list->offset == off)
@@ -303,14 +290,7 @@ addr_stridxptr (tree exp)
       list->next = XOBNEW (&stridx_obstack, struct stridxlist);
       list = list->next;
     }
-  else
-    {
-      struct decl_stridxlist_map *e
-	= XOBNEW (&stridx_obstack, struct decl_stridxlist_map);
-      e->base.from = base;
-      *slot = e;
-      list = &e->list;
-    }
+
   list->next = NULL;
   list->offset = off;
   list->idx = 0;
diff --git a/gcc/tree-ssa-uncprop.c b/gcc/tree-ssa-uncprop.c
index 81d30851f53..5c928b4f9e0 100644
--- a/gcc/tree-ssa-uncprop.c
+++ b/gcc/tree-ssa-uncprop.c
@@ -28,6 +28,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "basic-block.h"
 #include "function.h"
 #include "hash-table.h"
+#include "hash-map.h"
 #include "tree-ssa-alias.h"
 #include "internal-fn.h"
 #include "gimple-expr.h"
@@ -284,44 +285,38 @@ struct equiv_hash_elt
 
 /* Value to ssa name equivalence hashtable helpers.  */
 
-struct val_ssa_equiv_hasher
+struct val_ssa_equiv_hash_traits : default_hashmap_traits
 {
-  typedef equiv_hash_elt value_type;
-  typedef equiv_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 *);
+  static inline hashval_t hash (tree);
+  static inline bool equal_keys (tree, tree);
+  template<typename T> static inline void remove (T &);
 };
 
 inline hashval_t
-val_ssa_equiv_hasher::hash (const value_type *p)
+val_ssa_equiv_hash_traits::hash (tree value)
 {
-  tree const value = p->value;
   return iterative_hash_expr (value, 0);
 }
 
 inline bool
-val_ssa_equiv_hasher::equal (const value_type *p1, const compare_type *p2)
+val_ssa_equiv_hash_traits::equal_keys (tree value1, tree value2)
 {
-  tree value1 = p1->value;
-  tree value2 = p2->value;
-
   return operand_equal_p (value1, value2, 0);
 }
 
 /* Free an instance of equiv_hash_elt.  */
 
+template<typename T>
 inline void
-val_ssa_equiv_hasher::remove (value_type *elt)
+val_ssa_equiv_hash_traits::remove (T &elt)
 {
-  elt->equivalences.release ();
-  free (elt);
+  elt.m_value.release ();
 }
 
 /* Global hash table implementing a mapping from invariant values
    to a list of SSA_NAMEs which have the same value.  We might be
    able to reuse tree-vn for this code.  */
-static hash_table<val_ssa_equiv_hasher> *val_ssa_equiv;
+static hash_map<tree, vec<tree>, val_ssa_equiv_hash_traits> *val_ssa_equiv;
 
 static void uncprop_into_successor_phis (basic_block);
 
@@ -330,16 +325,7 @@ static void uncprop_into_successor_phis (basic_block);
 static void
 remove_equivalence (tree value)
 {
-  struct equiv_hash_elt an_equiv_elt, *an_equiv_elt_p;
-  equiv_hash_elt **slot;
-
-  an_equiv_elt.value = value;
-  an_equiv_elt.equivalences.create (0);
-
-  slot = val_ssa_equiv->find_slot (&an_equiv_elt, NO_INSERT);
-
-  an_equiv_elt_p = *slot;
-  an_equiv_elt_p->equivalences.pop ();
+    val_ssa_equiv->get (value)->pop ();
 }
 
 /* Record EQUIVALENCE = VALUE into our hash table.  */
@@ -347,23 +333,7 @@ remove_equivalence (tree value)
 static void
 record_equiv (tree value, tree equivalence)
 {
-  equiv_hash_elt *an_equiv_elt_p;
-  equiv_hash_elt **slot;
-
-  an_equiv_elt_p = XNEW (struct equiv_hash_elt);
-  an_equiv_elt_p->value = value;
-  an_equiv_elt_p->equivalences.create (0);
-
-  slot = val_ssa_equiv->find_slot (an_equiv_elt_p, INSERT);
-
-  if (*slot == NULL)
-    *slot = an_equiv_elt_p;
-  else
-     free (an_equiv_elt_p);
-
-  an_equiv_elt_p = *slot;
-
-  an_equiv_elt_p->equivalences.safe_push (equivalence);
+  val_ssa_equiv->get_or_insert (value).safe_push (equivalence);
 }
 
 class uncprop_dom_walker : public dom_walker
@@ -433,8 +403,6 @@ uncprop_into_successor_phis (basic_block bb)
 	  gimple phi = gsi_stmt (gsi);
 	  tree arg = PHI_ARG_DEF (phi, e->dest_idx);
 	  tree res = PHI_RESULT (phi);
-	  equiv_hash_elt an_equiv_elt;
-	  equiv_hash_elt **slot;
 
 	  /* If the argument is not an invariant and can be potentially
 	     coalesced with the result, then there's no point in
@@ -444,23 +412,17 @@ uncprop_into_successor_phis (basic_block bb)
 	    continue;
 
 	  /* Lookup this argument's value in the hash table.  */
-	  an_equiv_elt.value = arg;
-	  an_equiv_elt.equivalences.create (0);
-	  slot = val_ssa_equiv->find_slot (&an_equiv_elt, NO_INSERT);
-
-	  if (slot)
+	  vec<tree> *equivalences = val_ssa_equiv->get (arg);
+	  if (equivalences)
 	    {
-	      struct equiv_hash_elt *elt = *slot;
-	      int j;
-
 	      /* Walk every equivalence with the same value.  If we find
 		 one that can potentially coalesce with the PHI rsult,
 		 then replace the value in the argument with its equivalent
 		 SSA_NAME.  Use the most recent equivalence as hopefully
 		 that results in shortest lifetimes.  */
-	      for (j = elt->equivalences.length () - 1; j >= 0; j--)
+	      for (int j = equivalences->length () - 1; j >= 0; j--)
 		{
-		  tree equiv = elt->equivalences[j];
+		  tree equiv = (*equivalences)[j];
 
 		  if (gimple_can_coalesce_p (equiv, res))
 		    {
@@ -578,7 +540,8 @@ pass_uncprop::execute (function *fun)
   associate_equivalences_with_edges ();
 
   /* Create our global data structures.  */
-  val_ssa_equiv = new hash_table<val_ssa_equiv_hasher> (1024);
+  val_ssa_equiv
+    = new hash_map<tree, vec<tree>, val_ssa_equiv_hash_traits> (1024);
 
   /* We're going to do a dominator walk, so ensure that we have
      dominance information.  */
diff --git a/gcc/tree-streamer.c b/gcc/tree-streamer.c
index 517bf77f66b..17f304506ae 100644
--- a/gcc/tree-streamer.c
+++ b/gcc/tree-streamer.c
@@ -28,6 +28,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "tree-ssa-alias.h"
 #include "internal-fn.h"
 #include "gimple-expr.h"
+#include "hash-map.h"
 #include "is-a.h"
 #include "gimple.h"
 #include "streamer-hooks.h"
@@ -134,13 +135,11 @@ streamer_tree_cache_insert_1 (struct streamer_tree_cache_d *cache,
 			      tree t, hashval_t hash, unsigned *ix_p,
 			      bool insert_at_next_slot_p)
 {
-  unsigned *slot;
-  unsigned ix;
   bool existed_p;
 
   gcc_assert (t);
 
-  slot = cache->node_map->insert (t, &existed_p);
+  unsigned int &ix = cache->node_map->get_or_insert (t, &existed_p);
   if (!existed_p)
     {
       /* Determine the next slot to use in the cache.  */
@@ -148,14 +147,11 @@ streamer_tree_cache_insert_1 (struct streamer_tree_cache_d *cache,
 	ix = cache->next_idx++;
       else
 	ix = *ix_p;
-       *slot = ix;
 
       streamer_tree_cache_add_to_node_array (cache, ix, t, hash);
     }
   else
     {
-      ix = *slot;
-
       if (!insert_at_next_slot_p && ix != *ix_p)
 	{
 	  /* If the caller wants to insert T at a specific slot
@@ -163,7 +159,6 @@ streamer_tree_cache_insert_1 (struct streamer_tree_cache_d *cache,
 	     the requested location slot.  */
 	  ix = *ix_p;
 	  streamer_tree_cache_add_to_node_array (cache, ix, t, hash);
-	  *slot = ix;
 	}
     }
 
@@ -231,7 +226,7 @@ streamer_tree_cache_lookup (struct streamer_tree_cache_d *cache, tree t,
 
   gcc_assert (t);
 
-  slot = cache->node_map->contains (t);
+  slot = cache->node_map->get (t);
   if (slot == NULL)
     {
       retval = false;
@@ -332,7 +327,7 @@ streamer_tree_cache_create (bool with_hashes, bool with_map, bool with_vec)
   cache = XCNEW (struct streamer_tree_cache_d);
 
   if (with_map)
-    cache->node_map = new pointer_map<unsigned>;
+    cache->node_map = new hash_map<tree, unsigned> (251);
   cache->next_idx = 0;
   if (with_vec)
     cache->nodes.create (165);
@@ -356,8 +351,8 @@ streamer_tree_cache_delete (struct streamer_tree_cache_d *c)
   if (c == NULL)
     return;
 
-  if (c->node_map)
-    delete c->node_map;
+  delete c->node_map;
+  c->node_map = NULL;
   c->nodes.release ();
   c->hashes.release ();
   free (c);
diff --git a/gcc/tree-streamer.h b/gcc/tree-streamer.h
index 20dbba024f0..ddd366a92df 100644
--- a/gcc/tree-streamer.h
+++ b/gcc/tree-streamer.h
@@ -24,6 +24,7 @@ along with GCC; see the file COPYING3.  If not see
 
 #include "streamer-hooks.h"
 #include "lto-streamer.h"
+#include "hash-map.h"
 
 /* Cache of pickled nodes.  Used to avoid writing the same node more
    than once.  The first time a tree node is streamed out, it is
@@ -46,7 +47,7 @@ along with GCC; see the file COPYING3.  If not see
 struct streamer_tree_cache_d
 {
   /* The mapping between tree nodes and slots into the nodes array.  */
-  pointer_map<unsigned> *node_map;
+  hash_map<tree, unsigned> *node_map;
 
   /* The nodes pickled so far.  */
   vec<tree> nodes;