[3/3] add hash_map class

From: Trevor Saunders <tsaunders@mozilla.com>

Hi,

This patch adds a hash_map class so we can consolidate the boiler plate around
using hash_table as a map, it also allows us to get rid of pointer_map which I
do in this patch by converting its users to hash_map.

bootstrapped + regtested without regression on x86_64-unknown-linux-gnu, ok?

Trev

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.
	* 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.

lto/

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

On Fri, Jun 20, 2014 at 12:52 PM,  <tsaunders@mozilla.com> wrote:
> From: Trevor Saunders <tsaunders@mozilla.com>
>
> Hi,
>
> This patch adds a hash_map class so we can consolidate the boiler plate around
> using hash_table as a map, it also allows us to get rid of pointer_map which I
> do in this patch by converting its users to hash_map.
>
> bootstrapped + regtested without regression on x86_64-unknown-linux-gnu, ok?

Ok.

Thanks,
Richard.

> Trev
>
> 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.
>         * 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.
>
> lto/
>
>         * lto.c (canonical_type_hash_cache): Use hash_map instead of
>         pointer_map.
>
> diff --git a/gcc/alloc-pool.c b/gcc/alloc-pool.c
> index 49209ee..0d31835 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 7adec4f..be0a439 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 0000000..0b50f72
> --- /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 6926900..b1bc35e 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/lto-section-out.c b/gcc/lto-section-out.c
> index 9d6926c..00b1801 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 889e91d..566a0e0 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/lto.c b/gcc/lto/lto.c
> index 7c60981..78997b5 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;
>      }
>  }
>
> @@ -2921,7 +2919,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 a426534..fc59212 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 8158acc..40877ab 100644
> --- a/gcc/symtab.c
> +++ b/gcc/symtab.c
> @@ -874,7 +874,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)
>      {
> @@ -884,7 +884,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 b452d9d..dc659c9 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 81d3085..5c928b4 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 517bf77..17f3045 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 20dbba0..ddd366a 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;
> --
> 2.0.0
>

On 06/20/2014 12:52 PM, tsaunders@mozilla.com wrote:
> From: Trevor Saunders <tsaunders@mozilla.com>
>
> Hi,
>
> This patch adds a hash_map class so we can consolidate the boiler plate around
> using hash_table as a map, it also allows us to get rid of pointer_map which I
> do in this patch by converting its users to hash_map.

Hello Trev,
    I like your changes! One small question about pointer_set, which is unable of deletion of items. Do you plan to migrate and simplify hash_map to be a replacement for pointer_set?

Thanks,
Martin

>
> bootstrapped + regtested without regression on x86_64-unknown-linux-gnu, ok?
>
> Trev
>
> 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.
> 	* 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.
>
> lto/
>
> 	* lto.c (canonical_type_hash_cache): Use hash_map instead of
> 	pointer_map.
>
> diff --git a/gcc/alloc-pool.c b/gcc/alloc-pool.c
> index 49209ee..0d31835 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 7adec4f..be0a439 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 0000000..0b50f72
> --- /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 6926900..b1bc35e 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/lto-section-out.c b/gcc/lto-section-out.c
> index 9d6926c..00b1801 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 889e91d..566a0e0 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/lto.c b/gcc/lto/lto.c
> index 7c60981..78997b5 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;
>       }
>   }
>   
> @@ -2921,7 +2919,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 a426534..fc59212 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 8158acc..40877ab 100644
> --- a/gcc/symtab.c
> +++ b/gcc/symtab.c
> @@ -874,7 +874,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)
>       {
> @@ -884,7 +884,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 b452d9d..dc659c9 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 81d3085..5c928b4 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 517bf77..17f3045 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 20dbba0..ddd366a 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;

On Tue, Jun 24, 2014 at 02:29:53PM +0200, Martin Liška wrote:
> 
> On 06/20/2014 12:52 PM, tsaunders@mozilla.com wrote:
> >From: Trevor Saunders <tsaunders@mozilla.com>
> >
> >Hi,
> >
> >This patch adds a hash_map class so we can consolidate the boiler plate around
> >using hash_table as a map, it also allows us to get rid of pointer_map which I
> >do in this patch by converting its users to hash_map.
> 
> Hello Trev,
>    I like your changes! One small question about pointer_set, which is unable of deletion of items. Do you plan to migrate and simplify hash_map to be a replacement for pointer_set?

I'm not sure I follow the question.  I imagine that hash_map will
largely stay as it is, other than perhaps some const correctness stuff,
and supporting element removal at some point.  Supporting element
removal should be trivial since I'm just wrapping hash_table which
already supports it, but I didn't want to add it until there was code
testing it.  As you see in the patch I removed pointer_map so its
already a replacement for that functionality.  As for pointer_set since
its a set not a map hash_table would seem closer to me.

Trev


> 
> Thanks,
> Martin
> 
> >
> >bootstrapped + regtested without regression on x86_64-unknown-linux-gnu, ok?
> >
> >Trev
> >
> >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.
> >	* 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.
> >
> >lto/
> >
> >	* lto.c (canonical_type_hash_cache): Use hash_map instead of
> >	pointer_map.
> >
> >diff --git a/gcc/alloc-pool.c b/gcc/alloc-pool.c
> >index 49209ee..0d31835 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 7adec4f..be0a439 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 0000000..0b50f72
> >--- /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 6926900..b1bc35e 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/lto-section-out.c b/gcc/lto-section-out.c
> >index 9d6926c..00b1801 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 889e91d..566a0e0 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/lto.c b/gcc/lto/lto.c
> >index 7c60981..78997b5 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;
> >      }
> >  }
> >@@ -2921,7 +2919,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 a426534..fc59212 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 8158acc..40877ab 100644
> >--- a/gcc/symtab.c
> >+++ b/gcc/symtab.c
> >@@ -874,7 +874,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)
> >      {
> >@@ -884,7 +884,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 b452d9d..dc659c9 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 81d3085..5c928b4 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 517bf77..17f3045 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 20dbba0..ddd366a 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;
>

On 06/24/2014 02:40 PM, Trevor Saunders wrote:
> On Tue, Jun 24, 2014 at 02:29:53PM +0200, Martin Liška wrote:
>> On 06/20/2014 12:52 PM, tsaunders@mozilla.com wrote:
>>> From: Trevor Saunders <tsaunders@mozilla.com>
>>>
>>> Hi,
>>>
>>> This patch adds a hash_map class so we can consolidate the boiler plate around
>>> using hash_table as a map, it also allows us to get rid of pointer_map which I
>>> do in this patch by converting its users to hash_map.
>> Hello Trev,
>>     I like your changes! One small question about pointer_set, which is unable of deletion of items. Do you plan to migrate and simplify hash_map to be a replacement for pointer_set?
> I'm not sure I follow the question.  I imagine that hash_map will
> largely stay as it is, other than perhaps some const correctness stuff,
> and supporting element removal at some point.  Supporting element
> removal should be trivial since I'm just wrapping hash_table which
> already supports it, but I didn't want to add it until there was code
> testing it.  As you see in the patch I removed pointer_map so its
> already a replacement for that functionality.  As for pointer_set since
> its a set not a map hash_table would seem closer to me.
Understand, yeah, I was asking if we plan to add element removal also for (pointer_)set? I consider such functionality useful, but it looks  not related to your patch. If I understand correctly, you are not planning to use hash_* as wrapping data structure for set.

Martin

>
> Trev
>
>
>> Thanks,
>> Martin
>>
>>> bootstrapped + regtested without regression on x86_64-unknown-linux-gnu, ok?
>>>
>>> Trev
>>>
>>> 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.
>>> 	* 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.
>>>
>>> lto/
>>>
>>> 	* lto.c (canonical_type_hash_cache): Use hash_map instead of
>>> 	pointer_map.
>>>
>>> diff --git a/gcc/alloc-pool.c b/gcc/alloc-pool.c
>>> index 49209ee..0d31835 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 7adec4f..be0a439 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 0000000..0b50f72
>>> --- /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 6926900..b1bc35e 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/lto-section-out.c b/gcc/lto-section-out.c
>>> index 9d6926c..00b1801 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 889e91d..566a0e0 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/lto.c b/gcc/lto/lto.c
>>> index 7c60981..78997b5 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;
>>>       }
>>>   }
>>> @@ -2921,7 +2919,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 a426534..fc59212 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 8158acc..40877ab 100644
>>> --- a/gcc/symtab.c
>>> +++ b/gcc/symtab.c
>>> @@ -874,7 +874,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)
>>>       {
>>> @@ -884,7 +884,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 b452d9d..dc659c9 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 81d3085..5c928b4 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 517bf77..17f3045 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 20dbba0..ddd366a 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;

On Tue, Jun 24, 2014 at 03:17:46PM +0200, Martin Liška wrote:
> 
> On 06/24/2014 02:40 PM, Trevor Saunders wrote:
> >On Tue, Jun 24, 2014 at 02:29:53PM +0200, Martin Liška wrote:
> >>On 06/20/2014 12:52 PM, tsaunders@mozilla.com wrote:
> >>>From: Trevor Saunders <tsaunders@mozilla.com>
> >>>
> >>>Hi,
> >>>
> >>>This patch adds a hash_map class so we can consolidate the boiler plate around
> >>>using hash_table as a map, it also allows us to get rid of pointer_map which I
> >>>do in this patch by converting its users to hash_map.
> >>Hello Trev,
> >>    I like your changes! One small question about pointer_set, which is unable of deletion of items. Do you plan to migrate and simplify hash_map to be a replacement for pointer_set?
> >I'm not sure I follow the question.  I imagine that hash_map will
> >largely stay as it is, other than perhaps some const correctness stuff,
> >and supporting element removal at some point.  Supporting element
> >removal should be trivial since I'm just wrapping hash_table which
> >already supports it, but I didn't want to add it until there was code
> >testing it.  As you see in the patch I removed pointer_map so its
> >already a replacement for that functionality.  As for pointer_set since
> >its a set not a map hash_table would seem closer to me.
> Understand, yeah, I was asking if we plan to add element removal also for (pointer_)set? I consider such functionality useful, but it looks  not related to your patch. If I understand correctly, you are not planning to use hash_* as wrapping data structure for set.

correct, if anything I'd try and get rid of pointer_set, its not clear
to me how much it buys us over hash_table, and if we can't just make
hash_table do that.

Trev

> 
> Martin
> 
> >
> >Trev
> >
> >
> >>Thanks,
> >>Martin
> >>
> >>>bootstrapped + regtested without regression on x86_64-unknown-linux-gnu, ok?
> >>>
> >>>Trev
> >>>
> >>>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.
> >>>	* 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.
> >>>
> >>>lto/
> >>>
> >>>	* lto.c (canonical_type_hash_cache): Use hash_map instead of
> >>>	pointer_map.
> >>>
> >>>diff --git a/gcc/alloc-pool.c b/gcc/alloc-pool.c
> >>>index 49209ee..0d31835 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 7adec4f..be0a439 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 0000000..0b50f72
> >>>--- /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 6926900..b1bc35e 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/lto-section-out.c b/gcc/lto-section-out.c
> >>>index 9d6926c..00b1801 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 889e91d..566a0e0 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/lto.c b/gcc/lto/lto.c
> >>>index 7c60981..78997b5 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;
> >>>      }
> >>>  }
> >>>@@ -2921,7 +2919,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 a426534..fc59212 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 8158acc..40877ab 100644
> >>>--- a/gcc/symtab.c
> >>>+++ b/gcc/symtab.c
> >>>@@ -874,7 +874,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)
> >>>      {
> >>>@@ -884,7 +884,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 b452d9d..dc659c9 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 81d3085..5c928b4 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 517bf77..17f3045 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 20dbba0..ddd366a 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;
>

> 
> On 06/20/2014 12:52 PM, tsaunders@mozilla.com wrote:
> >From: Trevor Saunders <tsaunders@mozilla.com>
> >
> >Hi,
> >
> >This patch adds a hash_map class so we can consolidate the boiler plate around
> >using hash_table as a map, it also allows us to get rid of pointer_map which I
> >do in this patch by converting its users to hash_map.
> 
> Hello Trev,
>    I like your changes! One small question about pointer_set, which is unable of deletion of items. Do you plan to migrate and simplify hash_map to be a replacement for pointer_set?

Note that pointer-map use in LTO is quite performance critical. It would be good to double
check that the new use of hash does not produce slower code.

Honza

On Tue, Jun 24, 2014 at 08:23:49PM +0200, Jan Hubicka wrote:
> > 
> > On 06/20/2014 12:52 PM, tsaunders@mozilla.com wrote:
> > >From: Trevor Saunders <tsaunders@mozilla.com>
> > >
> > >Hi,
> > >
> > >This patch adds a hash_map class so we can consolidate the boiler plate around
> > >using hash_table as a map, it also allows us to get rid of pointer_map which I
> > >do in this patch by converting its users to hash_map.
> > 
> > Hello Trev,
> >    I like your changes! One small question about pointer_set, which is unable of deletion of items. Do you plan to migrate and simplify hash_map to be a replacement for pointer_set?
> 
> Note that pointer-map use in LTO is quite performance critical. It would be good to double
> check that the new use of hash does not produce slower code.

I believe the compiled code should be very similar, but I'll do  some
measuring to check.

Trev

> 
> Honza

On June 24, 2014 9:16:34 PM CEST, Trevor Saunders <tsaunders@mozilla.com> wrote:
>On Tue, Jun 24, 2014 at 08:23:49PM +0200, Jan Hubicka wrote:
>> > 
>> > On 06/20/2014 12:52 PM, tsaunders@mozilla.com wrote:
>> > >From: Trevor Saunders <tsaunders@mozilla.com>
>> > >
>> > >Hi,
>> > >
>> > >This patch adds a hash_map class so we can consolidate the boiler
>plate around
>> > >using hash_table as a map, it also allows us to get rid of
>pointer_map which I
>> > >do in this patch by converting its users to hash_map.
>> > 
>> > Hello Trev,
>> >    I like your changes! One small question about pointer_set, which
>is unable of deletion of items. Do you plan to migrate and simplify
>hash_map to be a replacement for pointer_set?
>> 
>> Note that pointer-map use in LTO is quite performance critical. It
>would be good to double
>> check that the new use of hash does not produce slower code.
>
>I believe the compiled code should be very similar, but I'll do  some
>measuring to check.

More important is memory use.

Richard.

>Trev
>
>> 
>> Honza

On 06/24/2014 09:31 PM, Richard Biener wrote:
> On June 24, 2014 9:16:34 PM CEST, Trevor Saunders <tsaunders@mozilla.com> wrote:
>> On Tue, Jun 24, 2014 at 08:23:49PM +0200, Jan Hubicka wrote:
>>>> On 06/20/2014 12:52 PM, tsaunders@mozilla.com wrote:
>>>>> From: Trevor Saunders <tsaunders@mozilla.com>
>>>>>
>>>>> Hi,
>>>>>
>>>>> This patch adds a hash_map class so we can consolidate the boiler
>> plate around
>>>>> using hash_table as a map, it also allows us to get rid of
>> pointer_map which I
>>>>> do in this patch by converting its users to hash_map.
>>>> Hello Trev,
>>>>     I like your changes! One small question about pointer_set, which
>> is unable of deletion of items. Do you plan to migrate and simplify
>> hash_map to be a replacement for pointer_set?
>>> Note that pointer-map use in LTO is quite performance critical. It
>> would be good to double
>>> check that the new use of hash does not produce slower code.
>> I believe the compiled code should be very similar, but I'll do  some
>> measuring to check.
> More important is memory use.
>
> Richard.
Hi,
    there's memory usage graph for current trunk and before Trevor's patchset. It looks there's no memory footprint regression.

https://drive.google.com/file/d/0B0pisUJ80pO1OG5uY28yNFRnWTA/edit?usp=sharing

Martin

>
>> Trev
>>
>>> Honza
>