On Wed, 15 Aug 2012, Lawrence Crowl wrote:
> On 8/15/12, Richard Henderson <r...@redhat.com> wrote:
> > On 2012-08-15 07:29, Richard Guenther wrote:
> >> + typedef typename Element::Element_t Element_t;
> >
> > Can we use something less ugly than Element_t?
> > Such as
> >
> > typedef typename Element::T T;
> >
> > ? Given that this name is scoped anyway...
>
> I do not much like _t names either.
The following is what I'm testing now, it also integrates the
hashtable support functions and typedef within the existing local
data types which is IMHO cleaner. (it also shows we can do with
a janitorial cleanup replacing typedef struct foo_d {} foo; with
struct foo {}; and the likes)
Bootstrap and regtest ongoing on x86_64-unknown-linux-gnu, ok?
Thanks,
Richard.
2012-08-16 Richard Guenther <rguent...@suse.de>
* hash-table.h (class hash_table): Use a descriptor template
argument instead of decomposed element type and support
functions.
(struct pointer_hash): New generic typed pointer-hash.
(struct typed_free_remove, struct typed_noop_remove): Generic
hash_table support pieces.
* coverage.c (struct counts_entry): Add hash_table support
members.
* tree-ssa-ccp.c (gimple_htab): Use pointer_hash.
* tree-ssa-coalesce.c (struct ssa_name_var_hash): New generic
SSA name by SSA_NAME_VAR hash.
(coalesce_ssa_name): Use it.
* tree-ssa-pre.c (struct pre_expr_d): Add hash_table support.
(expression_to_id): Adjust.
(struct expr_pred_trans_d): Add hash_table support.
(phi_translate_table): Adjust.
(phi_trans_lookup): Likewise.
(phi_trans_add): Likewise.
(do_regular_insertion): Likewise.
* tree-ssa-tail-merge.c (struct same_succ_def): Add hash_table
support.
(same_succ_htab): Adjust.
(find_same_succ_bb): Likewise.
(find_same_succ): Likewise.
(update_worklist): Likewise.
* tree-ssa-threadupdate.c (struct redirection_data): Add hash_table
support.
(redirection_data): Adjust.
Index: gcc/hash-table.h
===================================================================
*** gcc/hash-table.h.orig 2012-08-16 10:33:59.000000000 +0200
--- gcc/hash-table.h 2012-08-16 11:08:36.311277498 +0200
*************** xcallocator <Type>::data_free (Type *mem
*** 83,127 ****
}
! /* A common function for hashing a CANDIDATE typed pointer. */
template <typename Element>
! inline hashval_t
! typed_pointer_hash (const Element *candidate)
{
! /* This is a really poor hash function, but it is what the current code
uses,
! so I am reusing it to avoid an additional axis in testing. */
! return (hashval_t) ((intptr_t)candidate >> 3);
! }
!
! /* A common function for comparing an EXISTING and CANDIDATE typed pointers
! for equality. */
template <typename Element>
! inline int
! typed_pointer_equal (const Element *existing, const Element * candidate)
{
! return existing == candidate;
! }
! /* A common function for doing nothing on removing a RETIRED slot. */
template <typename Element>
! inline void
! typed_null_remove (Element *retired ATTRIBUTE_UNUSED)
{
! }
! /* A common function for using free on removing a RETIRED slot. */
template <typename Element>
! inline void
! typed_free_remove (Element *retired)
{
! free (retired);
}
--- 83,134 ----
}
! /* Remove method dispatching to free. */
template <typename Element>
! struct typed_free_remove
{
! static inline void remove (Element *p) { free (p); }
! };
! /* No-op remove method. */
template <typename Element>
! struct typed_noop_remove
{
! static inline void remove (Element *) {}
! };
! /* Pointer hash with a no-op remove method. */
template <typename Element>
! struct pointer_hash : typed_noop_remove <Element>
{
! typedef Element T;
+ static inline hashval_t
+ hash (const T *);
! static inline int
! equal (const T *existing, const T * candidate);
! };
template <typename Element>
! inline hashval_t
! pointer_hash<Element>::hash (const T *candidate)
{
! /* This is a really poor hash function, but it is what the current code
uses,
! so I am reusing it to avoid an additional axis in testing. */
! return (hashval_t) ((intptr_t)candidate >> 3);
! }
!
! template <typename Element>
! inline int
! pointer_hash<Element>::equal (const T *existing,
! const T *candidate)
! {
! return existing == candidate;
}
*************** extern hashval_t hash_table_mod2 (hashva
*** 147,157 ****
/* Internal implementation type. */
! template <typename Element>
struct hash_table_control
{
/* Table itself. */
! Element **entries;
/* Current size (in entries) of the hash table. */
size_t size;
--- 154,164 ----
/* Internal implementation type. */
! template <typename T>
struct hash_table_control
{
/* Table itself. */
! T **entries;
/* Current size (in entries) of the hash table. */
size_t size;
*************** struct hash_table_control
*** 180,194 ****
The table stores elements of type Element.
! It hashes elements with the Hash function.
The table currently works with relatively weak hash functions.
Use typed_pointer_hash <Element> when hashing pointers instead of
objects.
! It compares elements with the Equal function.
Two elements with the same hash may not be equal.
Use typed_pointer_equal <Element> when hashing pointers instead of
objects.
! It removes elements with the Remove function.
This feature is useful for freeing memory.
Use typed_null_remove <Element> when not freeing objects.
Use typed_free_remove <Element> when doing a simple object free.
--- 187,201 ----
The table stores elements of type Element.
! It hashes elements with the hash function.
The table currently works with relatively weak hash functions.
Use typed_pointer_hash <Element> when hashing pointers instead of
objects.
! It compares elements with the equal function.
Two elements with the same hash may not be equal.
Use typed_pointer_equal <Element> when hashing pointers instead of
objects.
! It removes elements with the remove function.
This feature is useful for freeing memory.
Use typed_null_remove <Element> when not freeing objects.
Use typed_free_remove <Element> when doing a simple object free.
*************** struct hash_table_control
*** 198,256 ****
*/
! template <typename Element,
! hashval_t (*Hash) (const Element *candidate),
! int (*Equal) (const Element *existing, const Element * candidate),
! void (*Remove) (Element *retired),
template <typename Type> class Allocator = xcallocator>
class hash_table
{
private:
! hash_table_control <Element> *htab;
!
! Element **find_empty_slot_for_expand (hashval_t hash);
void expand ();
public:
-
hash_table ();
void create (size_t initial_slots);
bool is_created ();
void dispose ();
! Element *find (Element *comparable);
! Element *find_with_hash (Element *comparable, hashval_t hash);
! Element **find_slot (Element *comparable, enum insert_option insert);
! Element **find_slot_with_hash (Element *comparable, hashval_t hash,
! enum insert_option insert);
void empty ();
! void clear_slot (Element **slot);
! void remove_elt (Element *comparable);
! void remove_elt_with_hash (Element *comparable, hashval_t hash);
size_t size();
size_t elements();
double collisions();
template <typename Argument,
! int (*Callback) (Element **slot, Argument argument)>
void traverse_noresize (Argument argument);
template <typename Argument,
! int (*Callback) (Element **slot, Argument argument)>
void traverse (Argument argument);
};
/* Construct the hash table. The only useful operation next is create. */
! template <typename Element,
! hashval_t (*Hash) (const Element *candidate),
! int (*Equal) (const Element *existing, const Element * candidate),
! void (*Remove) (Element *retired),
template <typename Type> class Allocator>
inline
! hash_table <Element, Hash, Equal, Remove, Allocator>::hash_table ()
: htab (NULL)
{
}
--- 205,257 ----
*/
! template <typename Descr,
template <typename Type> class Allocator = xcallocator>
class hash_table
{
+ public:
+ typedef typename Descr::T T;
private:
+ hash_table_control <T> *htab;
! T **find_empty_slot_for_expand (hashval_t hash);
void expand ();
public:
hash_table ();
void create (size_t initial_slots);
bool is_created ();
void dispose ();
! T *find (T *comparable);
! T *find_with_hash (T *comparable, hashval_t hash);
! T **find_slot (T *comparable, enum insert_option insert);
! T **find_slot_with_hash (T *comparable, hashval_t hash,
! enum insert_option insert);
void empty ();
! void clear_slot (T **slot);
! void remove_elt (T *comparable);
! void remove_elt_with_hash (T *comparable, hashval_t hash);
size_t size();
size_t elements();
double collisions();
template <typename Argument,
! int (*Callback) (T **slot, Argument argument)>
void traverse_noresize (Argument argument);
template <typename Argument,
! int (*Callback) (T **slot, Argument argument)>
void traverse (Argument argument);
};
/* Construct the hash table. The only useful operation next is create. */
! template <typename Descr,
template <typename Type> class Allocator>
inline
! hash_table <Descr, Allocator>::hash_table ()
: htab (NULL)
{
}
*************** hash_table <Element, Hash, Equal, Remove
*** 258,270 ****
/* See if the table has been created, as opposed to constructed. */
! template <typename Element,
! hashval_t (*Hash) (const Element *candidate),
! int (*Equal) (const Element *existing, const Element * candidate),
! void (*Remove) (Element *retired),
template <typename Type> class Allocator>
inline bool
! hash_table <Element, Hash, Equal, Remove, Allocator>::is_created ()
{
return htab != NULL;
}
--- 259,268 ----
/* See if the table has been created, as opposed to constructed. */
! template <typename Descr,
template <typename Type> class Allocator>
inline bool
! hash_table <Descr, Allocator>::is_created ()
{
return htab != NULL;
}
*************** hash_table <Element, Hash, Equal, Remove
*** 272,328 ****
/* Like find_with_hash, but compute the hash value from the element. */
! template <typename Element,
! hashval_t (*Hash) (const Element *candidate),
! int (*Equal) (const Element *existing, const Element * candidate),
! void (*Remove) (Element *retired),
template <typename Type> class Allocator>
! inline Element *
! hash_table <Element, Hash, Equal, Remove, Allocator>::find (Element
*comparable)
{
! return find_with_hash (comparable, Hash (comparable));
}
/* Like find_slot_with_hash, but compute the hash value from the element. */
! template <typename Element,
! hashval_t (*Hash) (const Element *candidate),
! int (*Equal) (const Element *existing, const Element * candidate),
! void (*Remove) (Element *retired),
! template <typename Type> class Allocator>
! inline Element **
! hash_table <Element, Hash, Equal, Remove, Allocator>
! ::find_slot (Element *comparable, enum insert_option insert)
{
! return find_slot_with_hash (comparable, Hash (comparable), insert);
}
/* Like remove_elt_with_hash, but compute the hash value from the element. */
! template <typename Element,
! hashval_t (*Hash) (const Element *candidate),
! int (*Equal) (const Element *existing, const Element * candidate),
! void (*Remove) (Element *retired),
template <typename Type> class Allocator>
inline void
! hash_table <Element, Hash, Equal, Remove, Allocator>
! ::remove_elt (Element *comparable)
{
! remove_elt_with_hash (comparable, Hash (comparable));
}
/* Return the current size of this hash table. */
! template <typename Element,
! hashval_t (*Hash) (const Element *candidate),
! int (*Equal) (const Element *existing, const Element * candidate),
! void (*Remove) (Element *retired),
template <typename Type> class Allocator>
inline size_t
! hash_table <Element, Hash, Equal, Remove, Allocator>::size()
{
return htab->size;
}
--- 270,314 ----
/* Like find_with_hash, but compute the hash value from the element. */
! template <typename Descr,
template <typename Type> class Allocator>
! inline typename Descr::T *
! hash_table <Descr, Allocator>::find (T *comparable)
{
! return find_with_hash (comparable, Descr::hash (comparable));
}
/* Like find_slot_with_hash, but compute the hash value from the element. */
! template <typename Descr,
! template <typename Type> class Allocator>
! inline typename Descr::T **
! hash_table <Descr, Allocator>
! ::find_slot (T *comparable, enum insert_option insert)
{
! return find_slot_with_hash (comparable, Descr::hash (comparable), insert);
}
/* Like remove_elt_with_hash, but compute the hash value from the element. */
! template <typename Descr,
template <typename Type> class Allocator>
inline void
! hash_table <Descr, Allocator>
! ::remove_elt (T *comparable)
{
! remove_elt_with_hash (comparable, Descr::hash (comparable));
}
/* Return the current size of this hash table. */
! template <typename Descr,
template <typename Type> class Allocator>
inline size_t
! hash_table <Descr, Allocator>::size()
{
return htab->size;
}
*************** hash_table <Element, Hash, Equal, Remove
*** 330,342 ****
/* Return the current number of elements in this hash table. */
! template <typename Element,
! hashval_t (*Hash) (const Element *candidate),
! int (*Equal) (const Element *existing, const Element * candidate),
! void (*Remove) (Element *retired),
template <typename Type> class Allocator>
inline size_t
! hash_table <Element, Hash, Equal, Remove, Allocator>::elements()
{
return htab->n_elements - htab->n_deleted;
}
--- 316,325 ----
/* Return the current number of elements in this hash table. */
! template <typename Descr,
template <typename Type> class Allocator>
inline size_t
! hash_table <Descr, Allocator>::elements()
{
return htab->n_elements - htab->n_deleted;
}
*************** hash_table <Element, Hash, Equal, Remove
*** 345,357 ****
/* Return the fraction of fixed collisions during all work with given
hash table. */
! template <typename Element,
! hashval_t (*Hash) (const Element *candidate),
! int (*Equal) (const Element *existing, const Element * candidate),
! void (*Remove) (Element *retired),
template <typename Type> class Allocator>
inline double
! hash_table <Element, Hash, Equal, Remove, Allocator>::collisions()
{
if (htab->searches == 0)
return 0.0;
--- 328,337 ----
/* Return the fraction of fixed collisions during all work with given
hash table. */
! template <typename Descr,
template <typename Type> class Allocator>
inline double
! hash_table <Descr, Allocator>::collisions()
{
if (htab->searches == 0)
return 0.0;
*************** hash_table <Element, Hash, Equal, Remove
*** 362,383 ****
/* Create a hash table with at least the given number of INITIAL_SLOTS. */
! template <typename Element,
! hashval_t (*Hash) (const Element *candidate),
! int (*Equal) (const Element *existing, const Element * candidate),
! void (*Remove) (Element *retired),
template <typename Type> class Allocator>
void
! hash_table <Element, Hash, Equal, Remove, Allocator>::create (size_t size)
{
unsigned int size_prime_index;
size_prime_index = hash_table_higher_prime_index (size);
size = prime_tab[size_prime_index].prime;
! htab = Allocator <hash_table_control <Element> > ::control_alloc (1);
gcc_assert (htab != NULL);
! htab->entries = Allocator <Element*> ::data_alloc (size);
gcc_assert (htab->entries != NULL);
htab->size = size;
htab->size_prime_index = size_prime_index;
--- 342,360 ----
/* Create a hash table with at least the given number of INITIAL_SLOTS. */
! template <typename Descr,
template <typename Type> class Allocator>
void
! hash_table <Descr, Allocator>::create (size_t size)
{
unsigned int size_prime_index;
size_prime_index = hash_table_higher_prime_index (size);
size = prime_tab[size_prime_index].prime;
! htab = Allocator <hash_table_control <T> > ::control_alloc (1);
gcc_assert (htab != NULL);
! htab->entries = Allocator <T*> ::data_alloc (size);
gcc_assert (htab->entries != NULL);
htab->size = size;
htab->size_prime_index = size_prime_index;
*************** hash_table <Element, Hash, Equal, Remove
*** 387,432 ****
/* Dispose of a hash table. Free all memory and return this hash table to
the non-created state. Naturally the hash table must already exist. */
! template <typename Element,
! hashval_t (*Hash) (const Element *candidate),
! int (*Equal) (const Element *existing, const Element * candidate),
! void (*Remove) (Element *retired),
template <typename Type> class Allocator>
void
! hash_table <Element, Hash, Equal, Remove, Allocator>::dispose ()
{
size_t size = htab->size;
! Element **entries = htab->entries;
for (int i = size - 1; i >= 0; i--)
if (entries[i] != HTAB_EMPTY_ENTRY && entries[i] != HTAB_DELETED_ENTRY)
! Remove (entries[i]);
! Allocator <Element *> ::data_free (entries);
! Allocator <hash_table_control <Element> > ::control_free (htab);
htab = NULL;
}
/* Similar to find_slot, but without several unwanted side effects:
! - Does not call Equal when it finds an existing entry.
- Does not change the count of elements/searches/collisions in the
hash table.
This function also assumes there are no deleted entries in the table.
HASH is the hash value for the element to be inserted. */
! template <typename Element,
! hashval_t (*Hash) (const Element *candidate),
! int (*Equal) (const Element *existing, const Element * candidate),
! void (*Remove) (Element *retired),
template <typename Type> class Allocator>
! Element **
! hash_table <Element, Hash, Equal, Remove, Allocator>
::find_empty_slot_for_expand (hashval_t hash)
{
hashval_t index = hash_table_mod1 (hash, htab->size_prime_index);
size_t size = htab->size;
! Element **slot = htab->entries + index;
hashval_t hash2;
if (*slot == HTAB_EMPTY_ENTRY)
--- 364,403 ----
/* Dispose of a hash table. Free all memory and return this hash table to
the non-created state. Naturally the hash table must already exist. */
! template <typename Descr,
template <typename Type> class Allocator>
void
! hash_table <Descr, Allocator>::dispose ()
{
size_t size = htab->size;
! T **entries = htab->entries;
for (int i = size - 1; i >= 0; i--)
if (entries[i] != HTAB_EMPTY_ENTRY && entries[i] != HTAB_DELETED_ENTRY)
! Descr::remove (entries[i]);
! Allocator <T *> ::data_free (entries);
! Allocator <hash_table_control <T> > ::control_free (htab);
htab = NULL;
}
/* Similar to find_slot, but without several unwanted side effects:
! - Does not call equal when it finds an existing entry.
- Does not change the count of elements/searches/collisions in the
hash table.
This function also assumes there are no deleted entries in the table.
HASH is the hash value for the element to be inserted. */
! template <typename Descr,
template <typename Type> class Allocator>
! typename Descr::T **
! hash_table <Descr, Allocator>
::find_empty_slot_for_expand (hashval_t hash)
{
hashval_t index = hash_table_mod1 (hash, htab->size_prime_index);
size_t size = htab->size;
! T **slot = htab->entries + index;
hashval_t hash2;
if (*slot == HTAB_EMPTY_ENTRY)
*************** hash_table <Element, Hash, Equal, Remove
*** 457,474 ****
table entries is changed. If memory allocation fails, this function
will abort. */
! template <typename Element,
! hashval_t (*Hash) (const Element *candidate),
! int (*Equal) (const Element *existing, const Element * candidate),
! void (*Remove) (Element *retired),
template <typename Type> class Allocator>
void
! hash_table <Element, Hash, Equal, Remove, Allocator>::expand ()
{
! Element **oentries;
! Element **olimit;
! Element **p;
! Element **nentries;
size_t nsize, osize, elts;
unsigned int oindex, nindex;
--- 428,442 ----
table entries is changed. If memory allocation fails, this function
will abort. */
! template <typename Descr,
template <typename Type> class Allocator>
void
! hash_table <Descr, Allocator>::expand ()
{
! T **oentries;
! T **olimit;
! T **p;
! T **nentries;
size_t nsize, osize, elts;
unsigned int oindex, nindex;
*************** hash_table <Element, Hash, Equal, Remove
*** 491,497 ****
nsize = osize;
}
! nentries = Allocator <Element *> ::data_alloc (nsize);
gcc_assert (nentries != NULL);
htab->entries = nentries;
htab->size = nsize;
--- 459,465 ----
nsize = osize;
}
! nentries = Allocator <T *> ::data_alloc (nsize);
gcc_assert (nentries != NULL);
htab->entries = nentries;
htab->size = nsize;
*************** hash_table <Element, Hash, Equal, Remove
*** 502,512 ****
p = oentries;
do
{
! Element *x = *p;
if (x != HTAB_EMPTY_ENTRY && x != HTAB_DELETED_ENTRY)
{
! Element **q = find_empty_slot_for_expand (Hash (x));
*q = x;
}
--- 470,480 ----
p = oentries;
do
{
! T *x = *p;
if (x != HTAB_EMPTY_ENTRY && x != HTAB_DELETED_ENTRY)
{
! T **q = find_empty_slot_for_expand (Descr::hash (x));
*q = x;
}
*************** hash_table <Element, Hash, Equal, Remove
*** 515,521 ****
}
while (p < olimit);
! Allocator <Element *> ::data_free (oentries);
}
--- 483,489 ----
}
while (p < olimit);
! Allocator <T *> ::data_free (oentries);
}
*************** hash_table <Element, Hash, Equal, Remove
*** 523,540 ****
COMPARABLE element starting with the given HASH value. It cannot
be used to insert or delete an element. */
! template <typename Element,
! hashval_t (*Hash) (const Element *candidate),
! int (*Equal) (const Element *existing, const Element * candidate),
! void (*Remove) (Element *retired),
! template <typename Type> class Allocator>
! Element *
! hash_table <Element, Hash, Equal, Remove, Allocator>
! ::find_with_hash (Element *comparable, hashval_t hash)
{
hashval_t index, hash2;
size_t size;
! Element *entry;
htab->searches++;
size = htab->size;
--- 491,505 ----
COMPARABLE element starting with the given HASH value. It cannot
be used to insert or delete an element. */
! template <typename Descr,
! template <typename Type> class Allocator>
! typename Descr::T *
! hash_table <Descr, Allocator>
! ::find_with_hash (T *comparable, hashval_t hash)
{
hashval_t index, hash2;
size_t size;
! T *entry;
htab->searches++;
size = htab->size;
*************** hash_table <Element, Hash, Equal, Remove
*** 542,548 ****
entry = htab->entries[index];
if (entry == HTAB_EMPTY_ENTRY
! || (entry != HTAB_DELETED_ENTRY && Equal (entry, comparable)))
return entry;
hash2 = hash_table_mod2 (hash, htab->size_prime_index);
--- 507,513 ----
entry = htab->entries[index];
if (entry == HTAB_EMPTY_ENTRY
! || (entry != HTAB_DELETED_ENTRY && Descr::equal (entry, comparable)))
return entry;
hash2 = hash_table_mod2 (hash, htab->size_prime_index);
*************** hash_table <Element, Hash, Equal, Remove
*** 555,561 ****
entry = htab->entries[index];
if (entry == HTAB_EMPTY_ENTRY
! || (entry != HTAB_DELETED_ENTRY && Equal (entry, comparable)))
return entry;
}
}
--- 520,526 ----
entry = htab->entries[index];
if (entry == HTAB_EMPTY_ENTRY
! || (entry != HTAB_DELETED_ENTRY && Descr::equal (entry,
comparable)))
return entry;
}
}
*************** hash_table <Element, Hash, Equal, Remove
*** 569,588 ****
write the value you want into the returned slot. When inserting an
entry, NULL may be returned if memory allocation fails. */
! template <typename Element,
! hashval_t (*Hash) (const Element *candidate),
! int (*Equal) (const Element *existing, const Element * candidate),
! void (*Remove) (Element *retired),
! template <typename Type> class Allocator>
! Element **
! hash_table <Element, Hash, Equal, Remove, Allocator>
! ::find_slot_with_hash (Element *comparable, hashval_t hash,
enum insert_option insert)
{
! Element **first_deleted_slot;
hashval_t index, hash2;
size_t size;
! Element *entry;
size = htab->size;
if (insert == INSERT && size * 3 <= htab->n_elements * 4)
--- 534,550 ----
write the value you want into the returned slot. When inserting an
entry, NULL may be returned if memory allocation fails. */
! template <typename Descr,
! template <typename Type> class Allocator>
! typename Descr::T **
! hash_table <Descr, Allocator>
! ::find_slot_with_hash (T *comparable, hashval_t hash,
enum insert_option insert)
{
! T **first_deleted_slot;
hashval_t index, hash2;
size_t size;
! T *entry;
size = htab->size;
if (insert == INSERT && size * 3 <= htab->n_elements * 4)
*************** hash_table <Element, Hash, Equal, Remove
*** 601,607 ****
goto empty_entry;
else if (entry == HTAB_DELETED_ENTRY)
first_deleted_slot = &htab->entries[index];
! else if (Equal (entry, comparable))
return &htab->entries[index];
hash2 = hash_table_mod2 (hash, htab->size_prime_index);
--- 563,569 ----
goto empty_entry;
else if (entry == HTAB_DELETED_ENTRY)
first_deleted_slot = &htab->entries[index];
! else if (Descr::equal (entry, comparable))
return &htab->entries[index];
hash2 = hash_table_mod2 (hash, htab->size_prime_index);
*************** hash_table <Element, Hash, Equal, Remove
*** 620,626 ****
if (!first_deleted_slot)
first_deleted_slot = &htab->entries[index];
}
! else if (Equal (entry, comparable))
return &htab->entries[index];
}
--- 582,588 ----
if (!first_deleted_slot)
first_deleted_slot = &htab->entries[index];
}
! else if (Descr::equal (entry, comparable))
return &htab->entries[index];
}
*************** hash_table <Element, Hash, Equal, Remove
*** 631,637 ****
if (first_deleted_slot)
{
htab->n_deleted--;
! *first_deleted_slot = static_cast <Element *> (HTAB_EMPTY_ENTRY);
return first_deleted_slot;
}
--- 593,599 ----
if (first_deleted_slot)
{
htab->n_deleted--;
! *first_deleted_slot = static_cast <T *> (HTAB_EMPTY_ENTRY);
return first_deleted_slot;
}
*************** hash_table <Element, Hash, Equal, Remove
*** 642,662 ****
/* This function clears all entries in the given hash table. */
! template <typename Element,
! hashval_t (*Hash) (const Element *candidate),
! int (*Equal) (const Element *existing, const Element * candidate),
! void (*Remove) (Element *retired),
template <typename Type> class Allocator>
void
! hash_table <Element, Hash, Equal, Remove, Allocator>::empty ()
{
size_t size = htab_size (htab);
! Element **entries = htab->entries;
int i;
for (i = size - 1; i >= 0; i--)
if (entries[i] != HTAB_EMPTY_ENTRY && entries[i] != HTAB_DELETED_ENTRY)
! Remove (entries[i]);
/* Instead of clearing megabyte, downsize the table. */
if (size > 1024*1024 / sizeof (PTR))
--- 604,621 ----
/* This function clears all entries in the given hash table. */
! template <typename Descr,
template <typename Type> class Allocator>
void
! hash_table <Descr, Allocator>::empty ()
{
size_t size = htab_size (htab);
! T **entries = htab->entries;
int i;
for (i = size - 1; i >= 0; i--)
if (entries[i] != HTAB_EMPTY_ENTRY && entries[i] != HTAB_DELETED_ENTRY)
! Descr::remove (entries[i]);
/* Instead of clearing megabyte, downsize the table. */
if (size > 1024*1024 / sizeof (PTR))
*************** hash_table <Element, Hash, Equal, Remove
*** 664,676 ****
int nindex = hash_table_higher_prime_index (1024 / sizeof (PTR));
int nsize = prime_tab[nindex].prime;
! Allocator <Element *> ::data_free (htab->entries);
! htab->entries = Allocator <Element *> ::data_alloc (nsize);
htab->size = nsize;
htab->size_prime_index = nindex;
}
else
! memset (entries, 0, size * sizeof (Element *));
htab->n_deleted = 0;
htab->n_elements = 0;
}
--- 623,635 ----
int nindex = hash_table_higher_prime_index (1024 / sizeof (PTR));
int nsize = prime_tab[nindex].prime;
! Allocator <T *> ::data_free (htab->entries);
! htab->entries = Allocator <T *> ::data_alloc (nsize);
htab->size = nsize;
htab->size_prime_index = nindex;
}
else
! memset (entries, 0, size * sizeof (T *));
htab->n_deleted = 0;
htab->n_elements = 0;
}
*************** hash_table <Element, Hash, Equal, Remove
*** 680,699 ****
useful when you've already done the lookup and don't want to do it
again. */
! template <typename Element,
! hashval_t (*Hash) (const Element *candidate),
! int (*Equal) (const Element *existing, const Element * candidate),
! void (*Remove) (Element *retired),
template <typename Type> class Allocator>
void
! hash_table <Element, Hash, Equal, Remove, Allocator>
! ::clear_slot (Element **slot)
{
if (slot < htab->entries || slot >= htab->entries + htab->size
|| *slot == HTAB_EMPTY_ENTRY || *slot == HTAB_DELETED_ENTRY)
abort ();
! Remove (*slot);
*slot = HTAB_DELETED_ENTRY;
htab->n_deleted++;
--- 639,655 ----
useful when you've already done the lookup and don't want to do it
again. */
! template <typename Descr,
template <typename Type> class Allocator>
void
! hash_table <Descr, Allocator>
! ::clear_slot (T **slot)
{
if (slot < htab->entries || slot >= htab->entries + htab->size
|| *slot == HTAB_EMPTY_ENTRY || *slot == HTAB_DELETED_ENTRY)
abort ();
! Descr::remove (*slot);
*slot = HTAB_DELETED_ENTRY;
htab->n_deleted++;
*************** hash_table <Element, Hash, Equal, Remove
*** 704,727 ****
from hash table starting with the given HASH. If there is no
matching element in the hash table, this function does nothing. */
! template <typename Element,
! hashval_t (*Hash) (const Element *candidate),
! int (*Equal) (const Element *existing, const Element * candidate),
! void (*Remove) (Element *retired),
template <typename Type> class Allocator>
void
! hash_table <Element, Hash, Equal, Remove, Allocator>
! ::remove_elt_with_hash (Element *comparable, hashval_t hash)
{
! Element **slot;
slot = find_slot_with_hash (comparable, hash, NO_INSERT);
if (*slot == HTAB_EMPTY_ENTRY)
return;
! Remove (*slot);
! *slot = static_cast <Element *> (HTAB_DELETED_ENTRY);
htab->n_deleted++;
}
--- 660,680 ----
from hash table starting with the given HASH. If there is no
matching element in the hash table, this function does nothing. */
! template <typename Descr,
template <typename Type> class Allocator>
void
! hash_table <Descr, Allocator>
! ::remove_elt_with_hash (T *comparable, hashval_t hash)
{
! T **slot;
slot = find_slot_with_hash (comparable, hash, NO_INSERT);
if (*slot == HTAB_EMPTY_ENTRY)
return;
! Descr::remove (*slot);
! *slot = static_cast <T *> (HTAB_DELETED_ENTRY);
htab->n_deleted++;
}
*************** hash_table <Element, Hash, Equal, Remove
*** 730,755 ****
each live entry. If CALLBACK returns false, the iteration stops.
ARGUMENT is passed as CALLBACK's second argument. */
! template <typename Element,
! hashval_t (*Hash) (const Element *candidate),
! int (*Equal) (const Element *existing, const Element * candidate),
! void (*Remove) (Element *retired),
template <typename Type> class Allocator>
template <typename Argument,
! int (*Callback) (Element **slot, Argument argument)>
void
! hash_table <Element, Hash, Equal, Remove, Allocator>
::traverse_noresize (Argument argument)
{
! Element **slot;
! Element **limit;
slot = htab->entries;
limit = slot + htab->size;
do
{
! Element *x = *slot;
if (x != HTAB_EMPTY_ENTRY && x != HTAB_DELETED_ENTRY)
if (! Callback (slot, argument))
--- 683,705 ----
each live entry. If CALLBACK returns false, the iteration stops.
ARGUMENT is passed as CALLBACK's second argument. */
! template <typename Descr,
template <typename Type> class Allocator>
template <typename Argument,
! int (*Callback) (typename Descr::T **slot, Argument argument)>
void
! hash_table <Descr, Allocator>
::traverse_noresize (Argument argument)
{
! T **slot;
! T **limit;
slot = htab->entries;
limit = slot + htab->size;
do
{
! T *x = *slot;
if (x != HTAB_EMPTY_ENTRY && x != HTAB_DELETED_ENTRY)
if (! Callback (slot, argument))
*************** hash_table <Element, Hash, Equal, Remove
*** 762,776 ****
/* Like traverse_noresize, but does resize the table when it is too empty
to improve effectivity of subsequent calls. */
! template <typename Element,
! hashval_t (*Hash) (const Element *candidate),
! int (*Equal) (const Element *existing, const Element * candidate),
! void (*Remove) (Element *retired),
template <typename Type> class Allocator>
template <typename Argument,
! int (*Callback) (Element **slot, Argument argument)>
void
! hash_table <Element, Hash, Equal, Remove, Allocator>
::traverse (Argument argument)
{
size_t size = htab->size;
--- 712,723 ----
/* Like traverse_noresize, but does resize the table when it is too empty
to improve effectivity of subsequent calls. */
! template <typename Descr,
template <typename Type> class Allocator>
template <typename Argument,
! int (*Callback) (typename Descr::T **slot, Argument argument)>
void
! hash_table <Descr, Allocator>
::traverse (Argument argument)
{
size_t size = htab->size;
Index: gcc/coverage.c
===================================================================
*** gcc/coverage.c.orig 2012-08-16 10:33:59.000000000 +0200
--- gcc/coverage.c 2012-08-16 10:54:30.986306770 +0200
*************** typedef struct counts_entry
*** 77,82 ****
--- 77,88 ----
unsigned cfg_checksum;
gcov_type *counts;
struct gcov_ctr_summary summary;
+
+ /* hash_table support. */
+ typedef counts_entry T;
+ static inline hashval_t hash (const counts_entry *);
+ static int equal (const counts_entry *, const counts_entry *);
+ static void remove (counts_entry *);
} counts_entry_t;
static GTY(()) struct coverage_data *functions_head = 0;
*************** get_gcov_unsigned_t (void)
*** 144,172 ****
}
inline hashval_t
! coverage_counts_entry_hash (const counts_entry_t *entry)
{
return entry->ident * GCOV_COUNTERS + entry->ctr;
}
inline int
! coverage_counts_entry_eq (const counts_entry_t *entry1,
! const counts_entry_t *entry2)
{
return entry1->ident == entry2->ident && entry1->ctr == entry2->ctr;
}
inline void
! coverage_counts_entry_del (counts_entry_t *entry)
{
free (entry->counts);
free (entry);
}
/* Hash table of count data. */
! static hash_table <counts_entry_t, coverage_counts_entry_hash,
! coverage_counts_entry_eq, coverage_counts_entry_del>
! counts_hash;
/* Read in the counts file, if available. */
--- 150,176 ----
}
inline hashval_t
! counts_entry::hash (const counts_entry_t *entry)
{
return entry->ident * GCOV_COUNTERS + entry->ctr;
}
inline int
! counts_entry::equal (const counts_entry_t *entry1,
! const counts_entry_t *entry2)
{
return entry1->ident == entry2->ident && entry1->ctr == entry2->ctr;
}
inline void
! counts_entry::remove (counts_entry_t *entry)
{
free (entry->counts);
free (entry);
}
/* Hash table of count data. */
! static hash_table <counts_entry> counts_hash;
/* Read in the counts file, if available. */
Index: gcc/tree-ssa-ccp.c
===================================================================
*** gcc/tree-ssa-ccp.c.orig 2012-08-16 10:33:59.000000000 +0200
--- gcc/tree-ssa-ccp.c 2012-08-16 10:34:56.175347440 +0200
*************** evaluate_stmt (gimple stmt)
*** 1688,1697 ****
return val;
}
! typedef hash_table <gimple_statement_d,
typed_pointer_hash<gimple_statement_d>,
! typed_pointer_equal<gimple_statement_d>,
! typed_null_remove<gimple_statement_d> >
! gimple_htab;
/* Given a BUILT_IN_STACK_SAVE value SAVED_VAL, insert a clobber of VAR before
each matching BUILT_IN_STACK_RESTORE. Mark visited phis in VISITED. */
--- 1688,1694 ----
return val;
}
! typedef hash_table <pointer_hash <gimple_statement_d> > gimple_htab;
/* Given a BUILT_IN_STACK_SAVE value SAVED_VAL, insert a clobber of VAR before
each matching BUILT_IN_STACK_RESTORE. Mark visited phis in VISITED. */
Index: gcc/tree-ssa-coalesce.c
===================================================================
*** gcc/tree-ssa-coalesce.c.orig 2012-08-16 10:33:59.000000000 +0200
--- gcc/tree-ssa-coalesce.c 2012-08-16 11:08:50.857277018 +0200
*************** coalesce_partitions (var_map map, ssa_co
*** 1258,1279 ****
}
}
! /* Returns a hash code for N. */
inline hashval_t
! hash_ssa_name_by_var (const_tree n)
{
! return (hashval_t) htab_hash_pointer (SSA_NAME_VAR (n));
}
- /* Returns nonzero if N1 and N2 are equal. */
-
inline int
! eq_ssa_name_by_var (const_tree n1, const_tree n2)
{
return SSA_NAME_VAR (n1) == SSA_NAME_VAR (n2);
}
/* Reduce the number of copies by coalescing variables in the function.
Return
a partition map with the resulting coalesces. */
--- 1258,1286 ----
}
}
!
! /* Hashtable support for storing SSA names hashed by their SSA_NAME_VAR. */
!
! struct ssa_name_var_hash : typed_noop_remove <union tree_node>
! {
! typedef union tree_node T;
! static inline hashval_t hash (const_tree);
! static inline int equal (const_tree, const_tree);
! };
inline hashval_t
! ssa_name_var_hash::hash (const_tree n)
{
! return DECL_UID (SSA_NAME_VAR (n));
}
inline int
! ssa_name_var_hash::equal (const_tree n1, const_tree n2)
{
return SSA_NAME_VAR (n1) == SSA_NAME_VAR (n2);
}
+
/* Reduce the number of copies by coalescing variables in the function.
Return
a partition map with the resulting coalesces. */
*************** coalesce_ssa_name (void)
*** 1286,1294 ****
bitmap used_in_copies = BITMAP_ALLOC (NULL);
var_map map;
unsigned int i;
! static hash_table <tree_node, hash_ssa_name_by_var, eq_ssa_name_by_var,
! typed_null_remove<tree_node> >
! ssa_name_hash;
cl = create_coalesce_list ();
map = create_outofssa_var_map (cl, used_in_copies);
--- 1293,1299 ----
bitmap used_in_copies = BITMAP_ALLOC (NULL);
var_map map;
unsigned int i;
! static hash_table <ssa_name_var_hash> ssa_name_hash;
cl = create_coalesce_list ();
map = create_outofssa_var_map (cl, used_in_copies);
Index: gcc/tree-ssa-pre.c
===================================================================
*** gcc/tree-ssa-pre.c.orig 2012-08-16 10:33:59.000000000 +0200
--- gcc/tree-ssa-pre.c 2012-08-16 11:09:12.132276244 +0200
*************** typedef union pre_expr_union_d
*** 165,175 ****
vn_reference_t reference;
} pre_expr_union;
! typedef struct pre_expr_d
{
enum pre_expr_kind kind;
unsigned int id;
pre_expr_union u;
} *pre_expr;
#define PRE_EXPR_NAME(e) (e)->u.name
--- 165,180 ----
vn_reference_t reference;
} pre_expr_union;
! typedef struct pre_expr_d : typed_noop_remove <pre_expr_d>
{
enum pre_expr_kind kind;
unsigned int id;
pre_expr_union u;
+
+ /* hash_table support. */
+ typedef pre_expr_d T;
+ static inline hashval_t hash (const pre_expr_d *);
+ static inline int equal (const pre_expr_d *, const pre_expr_d *);
} *pre_expr;
#define PRE_EXPR_NAME(e) (e)->u.name
*************** typedef struct pre_expr_d
*** 180,186 ****
/* Compare E1 and E1 for equality. */
inline int
! ssa_pre_expr_eq (const struct pre_expr_d *e1, const struct pre_expr_d *e2)
{
if (e1->kind != e2->kind)
return false;
--- 185,191 ----
/* Compare E1 and E1 for equality. */
inline int
! pre_expr_d::equal (const struct pre_expr_d *e1, const struct pre_expr_d *e2)
{
if (e1->kind != e2->kind)
return false;
*************** ssa_pre_expr_eq (const struct pre_expr_d
*** 205,211 ****
/* Hash E. */
inline hashval_t
! ssa_pre_expr_hash (const struct pre_expr_d *e)
{
switch (e->kind)
{
--- 210,216 ----
/* Hash E. */
inline hashval_t
! pre_expr_d::hash (const struct pre_expr_d *e)
{
switch (e->kind)
{
*************** static unsigned int next_expression_id;
*** 229,237 ****
DEF_VEC_P (pre_expr);
DEF_VEC_ALLOC_P (pre_expr, heap);
static VEC(pre_expr, heap) *expressions;
! static hash_table <pre_expr_d, ssa_pre_expr_hash, ssa_pre_expr_eq,
! typed_null_remove <pre_expr_d> >
! expression_to_id;
static VEC(unsigned, heap) *name_to_id;
/* Allocate an expression id for EXPR. */
--- 234,240 ----
DEF_VEC_P (pre_expr);
DEF_VEC_ALLOC_P (pre_expr, heap);
static VEC(pre_expr, heap) *expressions;
! static hash_table <pre_expr_d> expression_to_id;
static VEC(unsigned, heap) *name_to_id;
/* Allocate an expression id for EXPR. */
*************** static bitmap need_ab_cleanup;
*** 483,489 ****
/* A three tuple {e, pred, v} used to cache phi translations in the
phi_translate_table. */
! typedef struct expr_pred_trans_d
{
/* The expression. */
pre_expr e;
--- 486,492 ----
/* A three tuple {e, pred, v} used to cache phi translations in the
phi_translate_table. */
! typedef struct expr_pred_trans_d : typed_free_remove<expr_pred_trans_d>
{
/* The expression. */
pre_expr e;
*************** typedef struct expr_pred_trans_d
*** 497,519 ****
/* The hashcode for the expression, pred pair. This is cached for
speed reasons. */
hashval_t hashcode;
} *expr_pred_trans_t;
typedef const struct expr_pred_trans_d *const_expr_pred_trans_t;
- /* Return the hash value for a phi translation table entry. */
-
inline hashval_t
! ssa_expr_pred_trans_hash (const expr_pred_trans_d *ve)
{
! return ve->hashcode;
}
- /* Return true if two phi translation table entries are the same.
- P1 and P2 should point to the expr_pred_trans_t's to be compared.*/
-
inline int
! ssa_expr_pred_trans_eq (const expr_pred_trans_d *ve1,
! const expr_pred_trans_d *ve2)
{
basic_block b1 = ve1->pred;
basic_block b2 = ve2->pred;
--- 500,522 ----
/* The hashcode for the expression, pred pair. This is cached for
speed reasons. */
hashval_t hashcode;
+
+ /* hash_table support. */
+ typedef expr_pred_trans_d T;
+ static inline hashval_t hash (const expr_pred_trans_d *);
+ static inline int equal (const expr_pred_trans_d *, const expr_pred_trans_d
*);
} *expr_pred_trans_t;
typedef const struct expr_pred_trans_d *const_expr_pred_trans_t;
inline hashval_t
! expr_pred_trans_d::hash (const expr_pred_trans_d *e)
{
! return e->hashcode;
}
inline int
! expr_pred_trans_d::equal (const expr_pred_trans_d *ve1,
! const expr_pred_trans_d *ve2)
{
basic_block b1 = ve1->pred;
basic_block b2 = ve2->pred;
*************** ssa_expr_pred_trans_eq (const expr_pred_
*** 522,537 ****
be equal. */
if (b1 != b2)
return false;
! return ssa_pre_expr_eq (ve1->e, ve2->e);
}
/* The phi_translate_table caches phi translations for a given
expression and predecessor. */
!
! static hash_table <expr_pred_trans_d, ssa_expr_pred_trans_hash,
! ssa_expr_pred_trans_eq,
! typed_free_remove <expr_pred_trans_d> >
! phi_translate_table;
/* Search in the phi translation table for the translation of
expression E in basic block PRED.
--- 525,536 ----
be equal. */
if (b1 != b2)
return false;
! return pre_expr_d::equal (ve1->e, ve2->e);
}
/* The phi_translate_table caches phi translations for a given
expression and predecessor. */
! static hash_table <expr_pred_trans_d> phi_translate_table;
/* Search in the phi translation table for the translation of
expression E in basic block PRED.
*************** phi_trans_lookup (pre_expr e, basic_bloc
*** 545,551 ****
ept.e = e;
ept.pred = pred;
! ept.hashcode = iterative_hash_hashval_t (ssa_pre_expr_hash (e),
pred->index);
slot = phi_translate_table.find_slot_with_hash (&ept, ept.hashcode,
NO_INSERT);
if (!slot)
--- 544,550 ----
ept.e = e;
ept.pred = pred;
! ept.hashcode = iterative_hash_hashval_t (pre_expr_d::hash (e), pred->index);
slot = phi_translate_table.find_slot_with_hash (&ept, ept.hashcode,
NO_INSERT);
if (!slot)
*************** phi_trans_add (pre_expr e, pre_expr v, b
*** 566,572 ****
new_pair->e = e;
new_pair->pred = pred;
new_pair->v = v;
! new_pair->hashcode = iterative_hash_hashval_t (ssa_pre_expr_hash (e),
pred->index);
slot = phi_translate_table.find_slot_with_hash (new_pair,
--- 565,571 ----
new_pair->e = e;
new_pair->pred = pred;
new_pair->v = v;
! new_pair->hashcode = iterative_hash_hashval_t (pre_expr_d::hash (e),
pred->index);
slot = phi_translate_table.find_slot_with_hash (new_pair,
*************** do_regular_insertion (basic_block block,
*** 3495,3501 ****
do_insertion = true;
if (first_s == NULL)
first_s = edoubleprime;
! else if (!ssa_pre_expr_eq (first_s, edoubleprime))
all_same = false;
}
}
--- 3494,3500 ----
do_insertion = true;
if (first_s == NULL)
first_s = edoubleprime;
! else if (!pre_expr_d::equal (first_s, edoubleprime))
all_same = false;
}
}
Index: gcc/tree-ssa-tail-merge.c
===================================================================
*** gcc/tree-ssa-tail-merge.c.orig 2012-08-16 10:33:59.000000000 +0200
--- gcc/tree-ssa-tail-merge.c 2012-08-16 10:50:44.530314595 +0200
*************** struct same_succ_def
*** 224,233 ****
--- 224,247 ----
bool in_worklist;
/* The hash value of the struct. */
hashval_t hashval;
+
+ /* hash_table support. */
+ typedef same_succ_def T;
+ static inline hashval_t hash (const same_succ_def *);
+ static int equal (const same_succ_def *, const same_succ_def *);
+ static void remove (same_succ_def *);
};
typedef struct same_succ_def *same_succ;
typedef const struct same_succ_def *const_same_succ;
+ /* hash routine for hash_table support, returns hashval of E. */
+
+ inline hashval_t
+ same_succ_def::hash (const same_succ_def *e)
+ {
+ return e->hashval;
+ }
+
/* A group of bbs where 1 bb from bbs can replace the other bbs. */
struct bb_cluster_def
*************** stmt_update_dep_bb (gimple stmt)
*** 415,422 ****
/* Calculates hash value for same_succ VE. */
! hashval_t
! ssa_same_succ_hash (const_same_succ e)
{
hashval_t hashval = bitmap_hash (e->succs);
int flags;
--- 429,436 ----
/* Calculates hash value for same_succ VE. */
! static hashval_t
! same_succ_hash (const_same_succ e)
{
hashval_t hashval = bitmap_hash (e->succs);
int flags;
*************** inverse_flags (const_same_succ e1, const
*** 511,520 ****
return (f1a & mask) == (f2a & mask) && (f1b & mask) == (f2b & mask);
}
! /* Compares SAME_SUCCs VE1 and VE2. */
int
! ssa_same_succ_equal (const_same_succ e1, const_same_succ e2)
{
unsigned int i, first1, first2;
gimple_stmt_iterator gsi1, gsi2;
--- 525,534 ----
return (f1a & mask) == (f2a & mask) && (f1b & mask) == (f2b & mask);
}
! /* Compares SAME_SUCCs E1 and E2. */
int
! same_succ_def::equal (const_same_succ e1, const_same_succ e2)
{
unsigned int i, first1, first2;
gimple_stmt_iterator gsi1, gsi2;
*************** same_succ_alloc (void)
*** 584,593 ****
return same;
}
! /* Delete same_succ VE. */
! inline void
! ssa_same_succ_delete (same_succ e)
{
BITMAP_FREE (e->bbs);
BITMAP_FREE (e->succs);
--- 598,607 ----
return same;
}
! /* Delete same_succ E. */
! void
! same_succ_def::remove (same_succ e)
{
BITMAP_FREE (e->bbs);
BITMAP_FREE (e->succs);
*************** same_succ_reset (same_succ same)
*** 608,618 ****
VEC_truncate (int, same->succ_flags, 0);
}
! /* Hash table with all same_succ entries. */
!
! static hash_table <struct same_succ_def, ssa_same_succ_hash,
! ssa_same_succ_equal, ssa_same_succ_delete>
! same_succ_htab;
/* Array that is used to store the edge flags for a successor. */
--- 622,628 ----
VEC_truncate (int, same->succ_flags, 0);
}
! static hash_table <same_succ_def> same_succ_htab;
/* Array that is used to store the edge flags for a successor. */
*************** find_same_succ_bb (basic_block bb, same_
*** 692,698 ****
EXECUTE_IF_SET_IN_BITMAP (same->succs, 0, j, bj)
VEC_safe_push (int, heap, same->succ_flags, same_succ_edge_flags[j]);
! same->hashval = ssa_same_succ_hash (same);
slot = same_succ_htab.find_slot_with_hash (same, same->hashval, INSERT);
if (*slot == NULL)
--- 702,708 ----
EXECUTE_IF_SET_IN_BITMAP (same->succs, 0, j, bj)
VEC_safe_push (int, heap, same->succ_flags, same_succ_edge_flags[j]);
! same->hashval = same_succ_hash (same);
slot = same_succ_htab.find_slot_with_hash (same, same->hashval, INSERT);
if (*slot == NULL)
*************** find_same_succ (void)
*** 728,734 ****
same = same_succ_alloc ();
}
! ssa_same_succ_delete (same);
}
/* Initializes worklist administration. */
--- 738,744 ----
same = same_succ_alloc ();
}
! same_succ_def::remove (same);
}
/* Initializes worklist administration. */
*************** update_worklist (void)
*** 860,866 ****
if (same == NULL)
same = same_succ_alloc ();
}
! ssa_same_succ_delete (same);
bitmap_clear (deleted_bb_preds);
}
--- 870,876 ----
if (same == NULL)
same = same_succ_alloc ();
}
! same_succ_def::remove (same);
bitmap_clear (deleted_bb_preds);
}
Index: gcc/tree-ssa-threadupdate.c
===================================================================
*** gcc/tree-ssa-threadupdate.c.orig 2012-08-16 10:33:59.000000000 +0200
--- gcc/tree-ssa-threadupdate.c 2012-08-16 11:04:35.307285820 +0200
*************** struct el
*** 110,116 ****
may have many incoming edges threaded to the same outgoing edge. This
can be naturally implemented with a hash table. */
! struct redirection_data
{
/* A duplicate of B with the trailing control statement removed and which
targets a single successor of B. */
--- 110,116 ----
may have many incoming edges threaded to the same outgoing edge. This
can be naturally implemented with a hash table. */
! struct redirection_data : typed_free_remove<redirection_data>
{
/* A duplicate of B with the trailing control statement removed and which
targets a single successor of B. */
*************** struct redirection_data
*** 125,132 ****
--- 125,154 ----
/* A list of incoming edges which we want to thread to
OUTGOING_EDGE->dest. */
struct el *incoming_edges;
+
+ /* hash_table support. */
+ typedef redirection_data T;
+ static inline hashval_t hash (const redirection_data *);
+ static inline int equal (const redirection_data *, const redirection_data
*);
};
+ inline hashval_t
+ redirection_data::hash (const redirection_data *p)
+ {
+ edge e = p->outgoing_edge;
+ return e->dest->index;
+ }
+
+ inline int
+ redirection_data::equal (const redirection_data *p1, const redirection_data
*p2)
+ {
+ edge e1 = p1->outgoing_edge;
+ edge e2 = p2->outgoing_edge;
+ edge e3 = p1->intermediate_edge;
+ edge e4 = p2->intermediate_edge;
+ return e1 == e2 && e3 == e4;
+ }
+
/* Data structure of information to pass to hash table traversal routines. */
struct ssa_local_info_t
{
*************** create_block_for_threading (basic_block
*** 217,248 ****
rd->dup_block->count = 0;
}
- /* Hashing and equality routines for our hash table. */
- inline hashval_t
- ssa_redirection_data_hash (const struct redirection_data *p)
- {
- edge e = p->outgoing_edge;
- return e->dest->index;
- }
-
- inline int
- ssa_redirection_data_eq (const struct redirection_data *p1,
- const struct redirection_data *p2)
- {
- edge e1 = p1->outgoing_edge;
- edge e2 = p2->outgoing_edge;
- edge e3 = p1->intermediate_edge;
- edge e4 = p2->intermediate_edge;
-
- return e1 == e2 && e3 == e4;
- }
-
/* Main data structure to hold information for duplicates of BB. */
! static hash_table <struct redirection_data, ssa_redirection_data_hash,
! ssa_redirection_data_eq,
! typed_free_remove<struct redirection_data> >
! redirection_data;
/* Given an outgoing edge E lookup and return its entry in our hash table.
--- 239,247 ----
rd->dup_block->count = 0;
}
/* Main data structure to hold information for duplicates of BB. */
! static hash_table <redirection_data> redirection_data;
/* Given an outgoing edge E lookup and return its entry in our hash table.
