On Mon, Dec 17, 2012 at 9:01 PM, Lawrence Crowl <cr...@googlers.com> wrote:
> On 12/17/12, Richard Biener <richard.guent...@gmail.com> wrote:
>> On Mon, Dec 17, 2012 at 8:36 PM, Lawrence Crowl <cr...@googlers.com> wrote:
>>> Change tree-ssa-coalesce.c'coalesce_list_d.list from htab_t to
>>> hash_table.
>>>
>>> Fold coalesce_pair_map_hash and coalesce_pair_map_eq into new
>>> struct coalesce_pair_hasher.
>>>
>>> Removed struct coalesce_pair_iterator, as did not meet the hash_table
>>> iterator interface and it provided no significant code reduction.
>>>
>>> Tested on x86-64.
>>>
>>> Okay for branch?
>>>
>>>
>>> Index: gcc/tree-ssa-coalesce.c
>>> ===================================================================
>>> --- gcc/tree-ssa-coalesce.c (revision 194549)
>>> +++ gcc/tree-ssa-coalesce.c (working copy)
>>> @@ -50,6 +50,41 @@ typedef struct coalesce_pair
>>> } * coalesce_pair_p;
>>> typedef const struct coalesce_pair *const_coalesce_pair_p;
>>>
>>> +/* Coalesce pair hashtable helpers. */
>>> +
>>> +struct coalesce_pair_hasher : typed_noop_remove <coalesce_pair>
>>> +{
>>> + typedef coalesce_pair value_type;
>>> + typedef coalesce_pair compare_type;
>>> + static inline hashval_t hash (const value_type *);
>>> + static inline bool equal (const value_type *, const compare_type *);
>>> +};
>>> +
>>> +/* Hash function for coalesce list. Calculate hash for PAIR. */
>>> +
>>> +inline hashval_t
>>> +coalesce_pair_hasher::hash (const value_type *pair)
>>> +{
>>> + hashval_t a = (hashval_t)(pair->first_element);
>>> + hashval_t b = (hashval_t)(pair->second_element);
>>> +
>>> + return b * (b - 1) / 2 + a;
>>> +}
>>> +
>>> +/* Equality function for coalesce list hash table. Compare PAIR1 and
>>> PAIR2,
>>> + returning TRUE if the two pairs are equivalent. */
>>> +
>>> +inline bool
>>> +coalesce_pair_hasher::equal (const value_type *p1, const compare_type
>>> *p2)
>>> +{
>>> + return (p1->first_element == p2->first_element
>>> + && p1->second_element == p2->second_element);
>>> +}
>>> +
>>> +typedef hash_table <coalesce_pair_hasher> coalesce_table_type;
>>> +typedef coalesce_table_type::iterator coalesce_iterator_type;
>>> +
>>> +
>>> typedef struct cost_one_pair_d
>>> {
>>> int first_element;
>>> @@ -61,7 +96,7 @@ typedef struct cost_one_pair_d
>>>
>>> typedef struct coalesce_list_d
>>> {
>>> - htab_t list; /* Hash table. */
>>> + coalesce_table_type list; /* Hash table. */
>>> coalesce_pair_p *sorted; /* List when sorted. */
>>> int num_sorted; /* Number in the sorted list. */
>>> cost_one_pair_p cost_one_list;/* Single use coalesces with cost 1. */
>>> @@ -186,34 +221,6 @@ pop_best_coalesce (coalesce_list_p cl, i
>>> }
>>>
>>>
>>> -#define COALESCE_HASH_FN(R1, R2) ((R2) * ((R2) - 1) / 2 + (R1))
>>> -
>>> -/* Hash function for coalesce list. Calculate hash for PAIR. */
>>> -
>>> -static unsigned int
>>> -coalesce_pair_map_hash (const void *pair)
>>> -{
>>> - hashval_t a =
>>> (hashval_t)(((const_coalesce_pair_p)pair)->first_element);
>>> - hashval_t b =
>>> (hashval_t)(((const_coalesce_pair_p)pair)->second_element);
>>> -
>>> - return COALESCE_HASH_FN (a,b);
>>> -}
>>> -
>>> -
>>> -/* Equality function for coalesce list hash table. Compare PAIR1 and
>>> PAIR2,
>>> - returning TRUE if the two pairs are equivalent. */
>>> -
>>> -static int
>>> -coalesce_pair_map_eq (const void *pair1, const void *pair2)
>>> -{
>>> - const_coalesce_pair_p const p1 = (const_coalesce_pair_p) pair1;
>>> - const_coalesce_pair_p const p2 = (const_coalesce_pair_p) pair2;
>>> -
>>> - return (p1->first_element == p2->first_element
>>> - && p1->second_element == p2->second_element);
>>> -}
>>> -
>>> -
>>> /* Create a new empty coalesce list object and return it. */
>>>
>>> static inline coalesce_list_p
>>> @@ -226,8 +233,7 @@ create_coalesce_list (void)
>>> size = 40;
>>>
>>> list = (coalesce_list_p) xmalloc (sizeof (struct coalesce_list_d));
>>> - list->list = htab_create (size, coalesce_pair_map_hash,
>>> - coalesce_pair_map_eq, NULL);
>>> + list->list.create (size);
>>> list->sorted = NULL;
>>> list->num_sorted = 0;
>>> list->cost_one_list = NULL;
>>> @@ -241,7 +247,7 @@ static inline void
>>> delete_coalesce_list (coalesce_list_p cl)
>>> {
>>> gcc_assert (cl->cost_one_list == NULL);
>>> - htab_delete (cl->list);
>>> + cl->list.dispose ();
>>> free (cl->sorted);
>>> gcc_assert (cl->num_sorted == 0);
>>> free (cl);
>>> @@ -256,7 +262,7 @@ static coalesce_pair_p
>>> find_coalesce_pair (coalesce_list_p cl, int p1, int p2, bool create)
>>> {
>>> struct coalesce_pair p;
>>> - void **slot;
>>> + coalesce_pair **slot;
>>> unsigned int hash;
>>>
>>> /* Normalize so that p1 is the smaller value. */
>>> @@ -271,9 +277,8 @@ find_coalesce_pair (coalesce_list_p cl,
>>> p.second_element = p2;
>>> }
>>>
>>> - hash = coalesce_pair_map_hash (&p);
>>> - slot = htab_find_slot_with_hash (cl->list, &p, hash,
>>> - create ? INSERT : NO_INSERT);
>>> + hash = coalesce_pair_hasher::hash (&p);
>>> + slot = cl->list.find_slot_with_hash (&p, hash, create ? INSERT :
>>> NO_INSERT);
>>> if (!slot)
>>> return NULL;
>>>
>>> @@ -284,7 +289,7 @@ find_coalesce_pair (coalesce_list_p cl,
>>> pair->first_element = p.first_element;
>>> pair->second_element = p.second_element;
>>> pair->cost = 0;
>>> - *slot = (void *)pair;
>>> + *slot = pair;
>>> }
>>>
>>> return (struct coalesce_pair *) *slot;
>>> @@ -356,58 +361,10 @@ compare_pairs (const void *p1, const voi
>>> static inline int
>>> num_coalesce_pairs (coalesce_list_p cl)
>>> {
>>> - return htab_elements (cl->list);
>>> -}
>>> -
>>> -
>>> -/* Iterator over hash table pairs. */
>>> -typedef struct
>>> -{
>>> - htab_iterator hti;
>>> -} coalesce_pair_iterator;
>>> -
>>> -
>>> -/* Return first partition pair from list CL, initializing iterator ITER.
>>> */
>>> -
>>> -static inline coalesce_pair_p
>>> -first_coalesce_pair (coalesce_list_p cl, coalesce_pair_iterator *iter)
>>> -{
>>> - coalesce_pair_p pair;
>>> -
>>> - pair = (coalesce_pair_p) first_htab_element (&(iter->hti), cl->list);
>>> - return pair;
>>> -}
>>> -
>>> -
>>> -/* Return TRUE if there are no more partitions in for ITER to process.
>>> */
>>> -
>>> -static inline bool
>>> -end_coalesce_pair_p (coalesce_pair_iterator *iter)
>>> -{
>>> - return end_htab_p (&(iter->hti));
>>> -}
>>> -
>>> -
>>> -/* Return the next partition pair to be visited by ITER. */
>>> -
>>> -static inline coalesce_pair_p
>>> -next_coalesce_pair (coalesce_pair_iterator *iter)
>>> -{
>>> - coalesce_pair_p pair;
>>> -
>>> - pair = (coalesce_pair_p) next_htab_element (&(iter->hti));
>>> - return pair;
>>> + return cl->list.elements ();
>>> }
>>>
>>>
>>> -/* Iterate over CL using ITER, returning values in PAIR. */
>>> -
>>> -#define FOR_EACH_PARTITION_PAIR(PAIR, ITER, CL) \
>>> - for ((PAIR) = first_coalesce_pair ((CL), &(ITER)); \
>>> - !end_coalesce_pair_p (&(ITER)); \
>>> - (PAIR) = next_coalesce_pair (&(ITER)))
>>> -
>>> -
>>> /* Prepare CL for removal of preferred pairs. When finished they are
>>> sorted
>>> in order from most important coalesce to least important. */
>>>
>>> @@ -416,7 +373,7 @@ sort_coalesce_list (coalesce_list_p cl)
>>> {
>>> unsigned x, num;
>>> coalesce_pair_p p;
>>> - coalesce_pair_iterator ppi;
>>> + coalesce_iterator_type ppi;
>>>
>>> gcc_assert (cl->sorted == NULL);
>>>
>>> @@ -430,7 +387,7 @@ sort_coalesce_list (coalesce_list_p cl)
>>>
>>> /* Populate the vector with pointers to the pairs. */
>>> x = 0;
>>> - FOR_EACH_PARTITION_PAIR (p, ppi, cl)
>>> + FOR_EACH_HASH_TABLE_ELEMENT (cl->list, p, coalesce_pair_p, ppi)
>>
>> That's surely less descriptive than before. Just to point out
>> a case where my bad feelings about these mechanical changes have
>> a reason.
>
> Would you be happier if I added
>
> #define FOR_EACH_PARTITION_PAIR (p, ppi, cll) \
> FOR_EACH_HASH_TABLE_ELEMENT ((cll)->list, (p), coalesce_pair_p, (ppi))
>
> and used
>
> FOR_EACH_PARTITION_PAIR (p, ppi, cl->list)
>
> ?
Yeah, I guess so. But in most cases of these conversions I'd rather have
more surrounding code C++-ified, thus rather than just convert hashtables
refactor the immediate piece / data that uses a hashtable. Of course that's
a lot more work and requires thought and analysis of what the existing
code does.
But of course we agreed to not to translation to C++ just because it's possible
but to make the code better (in my sense better is equal to easier to
maintain and/or understand).
Ok, enough of ranting ... ;)
Richard.
>>> cl->sorted[x++] = p;
>>> gcc_assert (x == num);
>>>
>>> @@ -462,14 +419,15 @@ static void
>>> dump_coalesce_list (FILE *f, coalesce_list_p cl)
>>> {
>>> coalesce_pair_p node;
>>> - coalesce_pair_iterator ppi;
>>> + coalesce_iterator_type ppi;
>>> +
>>> int x;
>>> tree var;
>>>
>>> if (cl->sorted == NULL)
>>> {
>>> fprintf (f, "Coalesce List:\n");
>>> - FOR_EACH_PARTITION_PAIR (node, ppi, cl)
>>> + FOR_EACH_HASH_TABLE_ELEMENT (cl->list, node, coalesce_pair_p, ppi)
>>> {
>>> tree var1 = ssa_name (node->first_element);
>>> tree var2 = ssa_name (node->second_element);
>
> --
> Lawrence Crowl
