| Message ID | CAGqM8fZ9RZvhQSCwQ=7G2=Av3=ZqNsdR5yPY0U0uYGNwc2wAkQ@mail.gmail.com |
|---|---|
| State | New |
| Headers | show |
On Mon, Dec 17, 2012 at 8:36 PM, Lawrence Crowl <crowl@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. 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
On 12/17/12, Richard Biener <richard.guenther@gmail.com> wrote: > On Mon, Dec 17, 2012 at 8:36 PM, Lawrence Crowl <crowl@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) ? >> 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);
On Mon, Dec 17, 2012 at 9:01 PM, Lawrence Crowl <crowl@googlers.com> wrote: > On 12/17/12, Richard Biener <richard.guenther@gmail.com> wrote: >> On Mon, Dec 17, 2012 at 8:36 PM, Lawrence Crowl <crowl@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
On Tue, Dec 18, 2012 at 5:23 AM, Richard Biener <richard.guenther@gmail.com> wrote: > 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). This is not what this set of changes is doing. These are the mechanical side-effects of the new hash table design. We are not going to start re-writing the whole compiler by ourselves. We have set out to make very specific API changes and we are hoping that other maintainers will start contributing in their own areas. Easier to use hash tables make code easier to maintain and understand. Diego.
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) 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);