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, tsaund...@mozilla.com wrote: > >>>From: Trevor Saunders <tsaund...@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; >