This templates the pointer-map implementation (actually it copies
the implementation, leaving the old interface unchanged) providing
a templated value type. That's suitable to replace the various
users requesting a pointer-to-integer-type map, like I noticed
for the two LTO tree recording mechanisms. Which in turn saves
memory on 64bit hosts (and should be less heavy-weight on the cache).
Not very much, but a quarter of the old pointer-map memory usage.
LTO bootstrap and regtest running on x86_64-unknown-linux-gnu.
In theory we can typedef pointer_map<void *> pointer_map_t, but
that requires touching all pointer_map_t users to drop the
leading 'struct' and eventually include pointer-set.h.
I changed the insert () interface to get another output as to
whether the slot was present to avoid the need to have a special
"not present" value. That also makes it unnecessary to zero
the values array.
Any comments?
If not then I'll comb over existing pointer -> integer type map
users and convert them.
Thanks,
Richard.
2013-06-19 Richard Biener <rguent...@suse.de>
* pointer-set.h (struct pointer_map_base): New struct.
(class pointer_map): New template class implementing a
generic pointer to T map.
(pointer_map<T>::pointer_map, pointer_map<T>::~pointer_map,
pointer_map<T>::contains, pointer_map<T>::insert,
pointer_map<T>::traverse): New functions.
* pointer-set.c (pointer_map_base::lookup): New function.
* tree-streamer.h (struct streamer_tree_cache_d): Use a
pointer_map<unsigned> instead of a pointer_map_t.
* tree-streamer.c (streamer_tree_cache_insert_1): Adjust.
(streamer_tree_cache_lookup): Likewise.
(streamer_tree_cache_create): Likewise.
(streamer_tree_cache_delete): Likewise.
* lto-streamer.h (struct lto_tree_ref_encoder): Use a
pointer_map<unsigned> instead of a pointer_map_t.
(lto_init_tree_ref_encoder): Adjust.
(lto_destroy_tree_ref_encoder): Likewise.
* lto-section-out.c (lto_output_decl_index): Likewise.
(lto_record_function_out_decl_state): Likewise.
Index: gcc/pointer-set.c
===================================================================
*** gcc/pointer-set.c (revision 200189)
--- gcc/pointer-set.c (working copy)
*************** void pointer_map_traverse (const struct
*** 301,303 ****
--- 301,335 ----
if (pmap->keys[i] && !fn (pmap->keys[i], &pmap->values[i], data))
break;
}
+
+
+
+ /* Lookup the slot for the pointer P and return true if it exists,
+ otherwise return false in which case *IX points to the slot that
+ would be used on insertion. */
+
+ bool
+ pointer_map_base::lookup (const void *p, size_t *ix)
+ {
+ size_t n = hash1 (p, n_slots, log_slots);
+
+ while (true)
+ {
+ if (keys[n] == p)
+ {
+ *ix = n;
+ return true;
+ }
+ else if (keys[n] == 0)
+ {
+ *ix = n;
+ return false;
+ }
+ else
+ {
+ ++n;
+ if (n == n_slots)
+ n = 0;
+ }
+ }
+ }
Index: gcc/pointer-set.h
===================================================================
*** gcc/pointer-set.h (revision 200189)
--- gcc/pointer-set.h (working copy)
*************** void pointer_set_traverse (const struct
*** 30,42 ****
bool (*) (const void *, void *),
void *);
struct pointer_map_t;
! struct pointer_map_t *pointer_map_create (void);
! void pointer_map_destroy (struct pointer_map_t *pmap);
! void **pointer_map_contains (const struct pointer_map_t *pmap, const void *p);
! void **pointer_map_insert (struct pointer_map_t *pmap, const void *p);
! void pointer_map_traverse (const struct pointer_map_t *,
bool (*) (const void *, void **, void *), void *);
#endif /* POINTER_SET_H */
--- 30,166 ----
bool (*) (const void *, void *),
void *);
+
+ struct pointer_map_base
+ {
+ size_t log_slots;
+ size_t n_slots; /* n_slots = 2^log_slots */
+ size_t n_elements;
+ const void **keys;
+
+ bool lookup (const void *p, size_t *n);
+ };
+
+ /* 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_map_base
+ {
+ 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;
+
+ keys = XCNEWVEC (const void *, n_slots);
+ values = XCNEWVEC (T, n_slots);
+ }
+
+ /* Reclaims all memory associated with PMAP. */
+ template <typename T>
+ pointer_map<T>::~pointer_map (void)
+ {
+ XDELETEVEC (keys);
+ 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 (!lookup (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 = keys;
+ T *old_values = values;
+ log_slots = log_slots + 1;
+ n_slots = n_slots * 2;
+ keys = XCNEWVEC (const void *, n_slots);
+ values = XCNEWVEC (T, n_slots);
+ for (size_t i = 0; i < old_n_slots; ++i)
+ if (old_keys[i])
+ {
+ const void *key = old_keys[i];
+ lookup (key, &n);
+ keys[n] = key;
+ values[n] = old_values[i];
+ }
+ XDELETEVEC (old_keys);
+ XDELETEVEC (old_values);
+ }
+
+ if (!lookup (p, &n))
+ {
+ ++n_elements;
+ keys[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 (keys[i] && !fn (keys[i], &values[i], data))
+ break;
+ }
+
+
struct pointer_map_t;
! pointer_map_t *pointer_map_create (void);
! void pointer_map_destroy (pointer_map_t *pmap);
! void **pointer_map_contains (const pointer_map_t *pmap, const void *p);
! void **pointer_map_insert (pointer_map_t *pmap, const void *p);
! void pointer_map_traverse (const pointer_map_t *,
bool (*) (const void *, void **, void *), void *);
+
#endif /* POINTER_SET_H */
Index: gcc/tree-streamer.c
===================================================================
*** gcc/tree-streamer.c (revision 200189)
--- gcc/tree-streamer.c (working copy)
*************** streamer_tree_cache_insert_1 (struct str
*** 128,157 ****
tree t, hashval_t hash, unsigned *ix_p,
bool insert_at_next_slot_p)
{
! void **slot;
unsigned ix;
bool existed_p;
gcc_assert (t);
! slot = pointer_map_insert (cache->node_map, t);
! if (!*slot)
{
/* Determine the next slot to use in the cache. */
if (insert_at_next_slot_p)
ix = cache->nodes.length ();
else
ix = *ix_p;
! *slot = (void *)(size_t) (ix + 1);
streamer_tree_cache_add_to_node_array (cache, ix, t, hash);
-
- /* Indicate that the item was not present in the cache. */
- existed_p = false;
}
else
{
! ix = (size_t) *slot - 1;
if (!insert_at_next_slot_p && ix != *ix_p)
{
--- 128,154 ----
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);
! if (!existed_p)
{
/* Determine the next slot to use in the cache. */
if (insert_at_next_slot_p)
ix = cache->nodes.length ();
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)
{
*************** streamer_tree_cache_insert_1 (struct str
*** 160,170 ****
the requested location slot. */
ix = *ix_p;
streamer_tree_cache_add_to_node_array (cache, ix, t, hash);
! *slot = (void *)(size_t) (ix + 1);
}
-
- /* Indicate that T was already in the cache. */
- existed_p = true;
}
if (ix_p)
--- 157,164 ----
the requested location slot. */
ix = *ix_p;
streamer_tree_cache_add_to_node_array (cache, ix, t, hash);
! *slot = ix;
}
}
if (ix_p)
*************** bool
*** 225,237 ****
streamer_tree_cache_lookup (struct streamer_tree_cache_d *cache, tree t,
unsigned *ix_p)
{
! void **slot;
bool retval;
unsigned ix;
gcc_assert (t);
! slot = pointer_map_contains (cache->node_map, t);
if (slot == NULL)
{
retval = false;
--- 219,231 ----
streamer_tree_cache_lookup (struct streamer_tree_cache_d *cache, tree t,
unsigned *ix_p)
{
! unsigned *slot;
bool retval;
unsigned ix;
gcc_assert (t);
! slot = cache->node_map->contains (t);
if (slot == NULL)
{
retval = false;
*************** streamer_tree_cache_lookup (struct strea
*** 240,246 ****
else
{
retval = true;
! ix = (size_t) *slot - 1;
}
if (ix_p)
--- 234,240 ----
else
{
retval = true;
! ix = *slot;
}
if (ix_p)
*************** streamer_tree_cache_create (bool with_ha
*** 332,338 ****
cache = XCNEW (struct streamer_tree_cache_d);
if (with_map)
! cache->node_map = pointer_map_create ();
cache->nodes.create (165);
if (with_hashes)
cache->hashes.create (165);
--- 326,332 ----
cache = XCNEW (struct streamer_tree_cache_d);
if (with_map)
! cache->node_map = new pointer_map<unsigned>;
cache->nodes.create (165);
if (with_hashes)
cache->hashes.create (165);
*************** streamer_tree_cache_delete (struct strea
*** 355,361 ****
return;
if (c->node_map)
! pointer_map_destroy (c->node_map);
c->nodes.release ();
c->hashes.release ();
free (c);
--- 349,355 ----
return;
if (c->node_map)
! delete c->node_map;
c->nodes.release ();
c->hashes.release ();
free (c);
Index: gcc/tree-streamer.h
===================================================================
*** gcc/tree-streamer.h (revision 200189)
--- gcc/tree-streamer.h (working copy)
*************** along with GCC; see the file COPYING3.
*** 47,53 ****
struct streamer_tree_cache_d
{
/* The mapping between tree nodes and slots into the nodes array. */
! struct pointer_map_t *node_map;
/* The nodes pickled so far. */
vec<tree> nodes;
--- 47,53 ----
struct streamer_tree_cache_d
{
/* The mapping between tree nodes and slots into the nodes array. */
! pointer_map<unsigned> *node_map;
/* The nodes pickled so far. */
vec<tree> nodes;
Index: gcc/lto-streamer.h
===================================================================
*** gcc/lto-streamer.h (revision 200189)
--- gcc/lto-streamer.h (working copy)
*************** struct GTY(()) lto_tree_ref_table
*** 479,485 ****
struct lto_tree_ref_encoder
{
! pointer_map_t *tree_hash_table; /* Maps pointers to indices. */
vec<tree> trees; /* Maps indices to pointers. */
};
--- 479,485 ----
struct lto_tree_ref_encoder
{
! pointer_map<unsigned> *tree_hash_table; /* Maps pointers to indices. */
vec<tree> trees; /* Maps indices to pointers. */
};
*************** lto_tag_check_range (enum LTO_tags actua
*** 997,1003 ****
static inline void
lto_init_tree_ref_encoder (struct lto_tree_ref_encoder *encoder)
{
! encoder->tree_hash_table = pointer_map_create ();
encoder->trees.create (0);
}
--- 997,1003 ----
static inline void
lto_init_tree_ref_encoder (struct lto_tree_ref_encoder *encoder)
{
! encoder->tree_hash_table = new pointer_map<unsigned>;
encoder->trees.create (0);
}
*************** lto_destroy_tree_ref_encoder (struct lto
*** 1009,1015 ****
{
/* Hash table may be delete already. */
if (encoder->tree_hash_table)
! pointer_map_destroy (encoder->tree_hash_table);
encoder->trees.release ();
}
--- 1009,1015 ----
{
/* Hash table may be delete already. */
if (encoder->tree_hash_table)
! delete encoder->tree_hash_table;
encoder->trees.release ();
}
Index: gcc/lto-section-out.c
===================================================================
*** gcc/lto-section-out.c (revision 200189)
--- gcc/lto-section-out.c (working copy)
*************** lto_output_decl_index (struct lto_output
*** 225,244 ****
struct lto_tree_ref_encoder *encoder,
tree name, unsigned int *this_index)
{
! void **slot;
! int index;
bool new_entry_p = FALSE;
! slot = pointer_map_insert (encoder->tree_hash_table, name);
! if (*slot == NULL)
{
index = encoder->trees.length ();
! *slot = (void *)(uintptr_t) index;
encoder->trees.safe_push (name);
new_entry_p = TRUE;
}
else
! index = (uintptr_t) *slot;
if (obs)
streamer_write_uhwi_stream (obs, index);
--- 233,253 ----
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);
! 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);
*************** lto_record_function_out_decl_state (tree
*** 438,444 ****
for (i = 0; i < LTO_N_DECL_STREAMS; i++)
if (state->streams[i].tree_hash_table)
{
! pointer_map_destroy (state->streams[i].tree_hash_table);
state->streams[i].tree_hash_table = NULL;
}
state->fn_decl = fn_decl;
--- 447,453 ----
for (i = 0; i < LTO_N_DECL_STREAMS; i++)
if (state->streams[i].tree_hash_table)
{
! delete state->streams[i].tree_hash_table;
state->streams[i].tree_hash_table = NULL;
}
state->fn_decl = fn_decl;
