From patchwork Fri Jun 20 10:52:18 2014 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Trevor Saunders X-Patchwork-Id: 362156 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id AF20814003E for ; Fri, 20 Jun 2014 20:54:51 +1000 (EST) DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:from :to:cc:subject:date:message-id:in-reply-to:references; q=dns; s= default; b=cogVe0HqbxB0ZZQM/mSH7z5ydJM+byFEwi4MNopdC6wBKB0Lc5ibA C+hGSjORyIuthWT4R3vz+wTBtYAiWbkrpdK5hUBfd0xLmRa1F5ZaUn0ZRwr7k7gj Jibby9dx9go3r8MESJ2+008zu1mDngpBaPjNYpSFj9HUCvKS+FhUh4= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:from :to:cc:subject:date:message-id:in-reply-to:references; s= default; bh=hflREZjYILrELf86/KHa2UVncLg=; b=RvlfyXJmoVUC2qjtgjRT H6uxa82HJLnBDwaQISq5tkxv4T8XC9dEovQUFTTNFSL7wiuuaMoN4lcEAmBIotsu iTr8yMelxFaIr7Ad8U66QXz/I2pIyJaRYD9xapBjqFQVB8W8WKPe+DLGmfcRfegh 7Y4DYJYylyLG3A9fV2QDjz8= Received: (qmail 5446 invoked by alias); 20 Jun 2014 10:54:08 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org Received: (qmail 5383 invoked by uid 89); 20 Jun 2014 10:54:06 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-0.5 required=5.0 tests=AWL, BAYES_50, T_RP_MATCHES_RCVD autolearn=ham version=3.3.2 X-HELO: smtp.mozilla.org Received: from mx1.corp.phx1.mozilla.com (HELO smtp.mozilla.org) (63.245.216.69) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES256-GCM-SHA384 encrypted) ESMTPS; Fri, 20 Jun 2014 10:53:57 +0000 Received: from iceball.corp.tor1.mozilla.com (69-165-234-187.cable.teksavvy.com [69.165.234.187]) (Authenticated sender: tsaunders@mozilla.com) by mx1.mail.corp.phx1.mozilla.com (Postfix) with ESMTPSA id ED515F2F18; Fri, 20 Jun 2014 03:53:54 -0700 (PDT) From: tsaunders@mozilla.com To: gcc-patches@gcc.gnu.org Cc: Trevor Saunders Subject: [PATCH 3/3] add hash_map class Date: Fri, 20 Jun 2014 06:52:18 -0400 Message-Id: <1403261538-884-3-git-send-email-tsaunders@mozilla.com> In-Reply-To: <1403261538-884-1-git-send-email-tsaunders@mozilla.com> References: <1403261538-884-1-git-send-email-tsaunders@mozilla.com> X-IsSubscribed: yes From: Trevor Saunders 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. 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 -{ - 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_hash; +static hash_map *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 (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 (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 bbs, size_t dom_i; edge e; edge_iterator ei; - pointer_map *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 bbs, } /* Construct the graph G. */ - map = new pointer_map; + hash_map 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 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 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 +. */ + + +#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 + 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 + 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 static void remove (T &v) { v.~T (); } + + /* Mark the passed in entry as being deleted. */ + + template + static void + mark_deleted (T &e) + { + mark_key_deleted (e.m_key); + } + + /* Mark the passed in entry as being empty. */ + + template + static void + mark_empty (T &e) + { + mark_key_empty (e.m_key); + } + + /* Return true if the passed in entry is marked as deleted. */ + + template + static bool + is_deleted (T &e) + { + return e.m_key == (void *)1; + } + + /* Return true if the passed in entry is marked as empty. */ + + template static bool is_empty (T &e) { return e.m_key == NULL; } + +private: + template + static void + mark_key_deleted (T *&k) + { + k = static_cast (1); + } + + template + static void + mark_key_empty (T *&k) + { + k = static_cast (0); + } +}; + +template +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 + void traverse (Arg a) const + { + for (typename hash_table::iterator iter = m_table.begin (); + iter != m_table.end (); ++iter) + f ((*iter).m_key, (*iter).m_value, a); + } + +private: + hash_table 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 &map) + tree newgroup, hash_map &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 map; - pointer_map comdat_head_map; + hash_map map (251); + hash_map 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 *tree_hash_table; /* Maps pointers to indices. */ + hash_map *tree_hash_table; /* Maps pointers to indices. */ vec 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; + encoder->tree_hash_table = new hash_map (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 *canonical_type_hash_cache; +static hash_map *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 ; + canonical_type_hash_cache = new hash_map (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 -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 -pointer_map::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 -pointer_map::~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 -T * -pointer_map::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 -T * -pointer_map::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 -void -pointer_map::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 comdat_head_map; + hash_map 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 +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 *decl_to_stridxlist_htab; +static hash_map + *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 (64); + decl_to_stridxlist_htab + = new hash_map (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 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 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; +static hash_map, 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 *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 (1024); + val_ssa_equiv + = new hash_map, 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; + cache->node_map = new hash_map (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 *node_map; + hash_map *node_map; /* The nodes pickled so far. */ vec nodes;