This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Out Of SSA Rewrite - Coalesce hash table patch


  This patch changes the coalesce list from a linked list representation
to a hash table implementation.  Nothing particularly fascinating or
interesting.  I fooled around with numerous hash functions, and this one
seems to work as well/better than most. 

  bootstrapped and regression tested on i686-pc-linux-gnu.

Andrew


	* tree-ssa-live.c (create_coalesce_list): Create a hash table.
	(COALESCE_HASH_FN): New.  Define hash function.
	(partition_pair_map_hash): New.  Hash value for a partition pair.
	(partition_pair_map_eq): New.  Equality for hash pairs.
	(create_coalesce_list): Create hash table.
	(delete_coalesce_list): Free hash table.
	(find_partition_pair): Find/create pairs in hash table.
	(compare_pairs):  Sort pairs in ascending order now.
	(num_coalesce_pairs): New.  Number of pairs in hash table.
	(struct partition_pair_iterator): Iterator struct for pair table.
	(first_partition_pair): Iterator function for first pair.
	(end_partition_pair_p): Iterator function for end of iteration.
	(next_partition_pair): Iterator function for next pair.
	(FOR_EACH_PARTITION_PAIR): Macro for iterating over pairs.
	(sort_coalesce_list): Sort pairs from hash table into an array.
	(pop_best_coalesce): Take pairs from the array.
	(dump_coalesce_list): Update to use hash table or sorted array.
	* tree-ssa-live.h (struct partition_pair_d): Remove next field.
	(struct coalesce_list_d): Add hash table related fields.



Index: tree-ssa-live.c
===================================================================
*** tree-ssa-live.c	(revision 118519)
--- tree-ssa-live.c	(working copy)
*************** type_var_init (var_map map)
*** 1136,1154 ****
  }
  
  
  /* Create a new coalesce list object from MAP and return it.  */
  
  coalesce_list_p 
  create_coalesce_list (var_map map)
  {
    coalesce_list_p list;
  
!   list = (coalesce_list_p) xmalloc (sizeof (struct coalesce_list_d));
  
    list->map = map;
    list->add_mode = true;
!   list->list = (partition_pair_p *) xcalloc (num_var_partitions (map),
! 					     sizeof (struct partition_pair_d));
    return list;
  }
  
--- 1136,1189 ----
  }
  
  
+ /* Hash function for 2 integer coalesce pairs.  */
+ #define COALESCE_HASH_FN(R1, R2) ((R2) * ((R2) - 1) / 2 + (R1))
+ 
+ 
+ /* Return hash value for partition pair PAIR.  */
+ 
+ unsigned int 
+ partition_pair_map_hash (const void *pair)
+ {
+   hashval_t a = (hashval_t)(((partition_pair_p)pair)->first_partition);
+   hashval_t b = (hashval_t)(((partition_pair_p)pair)->second_partition);
+ 
+   return COALESCE_HASH_FN (a,b);
+ }
+ 
+ 
+ /* Return TRUE if PAIR1 is equivilent to PAIR2.  */
+ 
+ int 
+ partition_pair_map_eq (const void *pair1, const void *pair2)
+ {
+   partition_pair_p p1 = (partition_pair_p) pair1;
+   partition_pair_p p2 = (partition_pair_p) pair2;
+ 
+   return (p1->first_partition == p2->first_partition
+ 	  && p1->second_partition == p2->second_partition);
+ }
+ 
+ 
  /* Create a new coalesce list object from MAP and return it.  */
  
  coalesce_list_p 
  create_coalesce_list (var_map map)
  {
    coalesce_list_p list;
+   unsigned size = num_ssa_names * 3;
+ 
+   if (size < 40)
+     size = 40;
  
!   list = xmalloc (sizeof (struct coalesce_list_d));
!   list->list = htab_create (size, partition_pair_map_hash,
!   			    partition_pair_map_eq, NULL);
  
    list->map = map;
+   list->sorted = NULL;
    list->add_mode = true;
!   list->num_sorted = 0;
    return list;
  }
  
*************** create_coalesce_list (var_map map)
*** 1158,1164 ****
  void 
  delete_coalesce_list (coalesce_list_p cl)
  {
!   free (cl->list);
    free (cl);
  }
  
--- 1193,1202 ----
  void 
  delete_coalesce_list (coalesce_list_p cl)
  {
!   htab_delete (cl->list);
!   if (cl->sorted)
!     free (cl->sorted);
!   gcc_assert (cl->num_sorted == 0);
    free (cl);
  }
  
*************** delete_coalesce_list (coalesce_list_p cl
*** 1170,1221 ****
  static partition_pair_p
  find_partition_pair (coalesce_list_p cl, int p1, int p2, bool create)
  {
!   partition_pair_p node, tmp;
!   int s;
      
!   /* Normalize so that p1 is the smaller value.  */
    if (p2 < p1)
      {
!       s = p1;
!       p1 = p2;
!       p2 = s;
      }
!   
!   tmp = NULL;
! 
!   /* The list is sorted such that if we find a value greater than p2,
!      p2 is not in the list.  */
!   for (node = cl->list[p1]; node; node = node->next)
      {
!       if (node->second_partition == p2)
!         return node;
!       else
!         if (node->second_partition > p2)
! 	  break;
!      tmp = node;
      }
  
!   if (!create)
!     return NULL;
! 
!   node = (partition_pair_p) xmalloc (sizeof (struct partition_pair_d));
!   node->first_partition = p1;
!   node->second_partition = p2;
!   node->cost = 0;
!     
!   if (tmp != NULL)
      {
!       node->next = tmp->next;
!       tmp->next = node;
!     }
!   else
!     {
!       /* This is now the first node in the list.  */
!       node->next = cl->list[p1];
!       cl->list[p1] = node;
      }
  
!   return node;
  }
  
  /* Return cost of execution of copy instruction with FREQUENCY
--- 1208,1245 ----
  static partition_pair_p
  find_partition_pair (coalesce_list_p cl, int p1, int p2, bool create)
  {
!   struct partition_pair p, *pair;
!   void **slot;
!   unsigned int hash;
      
!   /* normalize so that p1 is the smaller value.  */
    if (p2 < p1)
      {
!       p.first_partition = p2;
!       p.second_partition = p1;
      }
!   else
      {
!       p.first_partition = p1;
!       p.second_partition = p2;
      }
+   
+   
+   hash = partition_pair_map_hash (&p);
+   pair = (struct partition_pair *) htab_find_with_hash (cl->list, &p, hash);
  
!   if (create && !pair)
      {
!       gcc_assert (cl->add_mode);
!       pair = xmalloc (sizeof (struct partition_pair));
!       pair->first_partition = p.first_partition;
!       pair->second_partition = p.second_partition;
!       pair->cost = 0;
!       slot = htab_find_slot_with_hash (cl->list, pair, hash, INSERT);
!       *(struct partition_pair **)slot = pair;
      }
  
!   return pair;
  }
  
  /* Return cost of execution of copy instruction with FREQUENCY
*************** add_coalesce (coalesce_list_p cl, int p1
*** 1256,1270 ****
  }
  
  
! /* Comparison function to allow qsort to sort P1 and P2 in descending order.  */
  
  static
  int compare_pairs (const void *p1, const void *p2)
  {
!   return (*(partition_pair_p *)p2)->cost - (*(partition_pair_p *)p1)->cost;
  }
  
  
  /* Prepare CL for removal of preferred pairs.  When finished, list element 
     0 has all the coalesce pairs, sorted in order from most important coalesce 
     to least important.  */
--- 1280,1335 ----
  }
  
  
! /* Comparison function to allow qsort to sort P1 and P2 in Ascendiong order.  */
  
  static
  int compare_pairs (const void *p1, const void *p2)
  {
!   return (*(partition_pair_p *)p1)->cost - (*(partition_pair_p *)p2)->cost;
  }
  
  
+ static inline int
+ num_coalesce_pairs (coalesce_list_p cl)
+ {
+   return htab_elements (cl->list);
+ }
+ 
+ typedef struct
+ {
+   htab_iterator hti;
+ } partition_pair_iterator;
+ 
+ static inline partition_pair_p
+ first_partition_pair (coalesce_list_p cl, partition_pair_iterator *iter)
+ {
+   partition_pair_p pair;
+ 
+   pair = (partition_pair_p) first_htab_element (&(iter->hti), cl->list);
+   return pair;
+ }
+ 
+ static inline bool
+ end_partition_pair_p (partition_pair_iterator *iter)
+ {
+   return end_htab_p (&(iter->hti));
+ }
+ 
+ static inline partition_pair_p
+ next_partition_pair (partition_pair_iterator *iter)
+ {
+   partition_pair_p pair;
+ 
+   pair = (partition_pair_p) next_htab_element (&(iter->hti));
+   return pair;
+ }
+ 
+ #define FOR_EACH_PARTITION_PAIR(PAIR, ITER, CL)		\
+   for ((PAIR) = first_partition_pair ((CL), &(ITER));	\
+        !end_partition_pair_p (&(ITER));			\
+        (PAIR) = next_partition_pair (&(ITER)))
+ 
+ 
  /* Prepare CL for removal of preferred pairs.  When finished, list element 
     0 has all the coalesce pairs, sorted in order from most important coalesce 
     to least important.  */
*************** int compare_pairs (const void *p1, const
*** 1272,1335 ****
  void
  sort_coalesce_list (coalesce_list_p cl)
  {
!   unsigned x, num, count;
!   partition_pair_p chain, p;
!   partition_pair_p  *list;
  
    gcc_assert (cl->add_mode);
  
    cl->add_mode = false;
  
!   /* Compact the array of lists to a single list, and count the elements.  */
!   num = 0;
!   chain = NULL;
!   for (x = 0; x < num_var_partitions (cl->map); x++)
!     if (cl->list[x] != NULL)
!       {
!         for (p = cl->list[x]; p->next != NULL; p = p->next)
! 	  num++;
! 	num++;
! 	p->next = chain;
! 	chain = cl->list[x];
! 	cl->list[x] = NULL;
!       }
  
!   /* Only call qsort if there are more than 2 items.  */
!   if (num > 2)
!     {
!       list = XNEWVEC (partition_pair_p, num);
!       count = 0;
!       for (p = chain; p != NULL; p = p->next)
! 	list[count++] = p;
! 
!       gcc_assert (count == num);
! 	
!       qsort (list, count, sizeof (partition_pair_p), compare_pairs);
  
!       p = list[0];
!       for (x = 1; x < num; x++)
! 	{
! 	  p->next = list[x];
! 	  p = list[x];
! 	}
!       p->next = NULL;
!       cl->list[0] = list[0];
!       free (list);
!     }
!   else
      {
!       cl->list[0] = chain;
!       if (num == 2)
! 	{
! 	  /* Simply swap the two elements if they are in the wrong order.  */
! 	  if (chain->cost < chain->next->cost)
! 	    {
! 	      cl->list[0] = chain->next;
! 	      cl->list[0]->next = chain;
! 	      chain->next = NULL;
! 	    }
  	}
      }
  }
  
  
--- 1337,1381 ----
  void
  sort_coalesce_list (coalesce_list_p cl)
  {
!   unsigned x, num;
!   partition_pair_p p;
!   partition_pair_iterator ppi;
  
    gcc_assert (cl->add_mode);
  
    cl->add_mode = false;
  
!   /* allocate a vector for the pair pointers.  */
!   num = num_coalesce_pairs (cl);
!   cl->num_sorted = num;
!   if (num == 0)
!     return;
!   cl->sorted = XNEWVEC (partition_pair_p, num);
  
!   /* Populate the vector with pointers to the partition pairs.  */
!   
!   x = 0;
!   FOR_EACH_PARTITION_PAIR (p, ppi, cl)
!     cl->sorted[x++] = p;
!   gcc_assert (x == num);
  
!   if (num == 1)
!     return;
! 
!   if (num == 2)
      {
!       if (cl->sorted[0]->cost > cl->sorted[1]->cost)
!         {
! 	  p = cl->sorted[0];
! 	  cl->sorted[0] = cl->sorted[1];
! 	  cl->sorted[1] = p;
  	}
+       return;
      }
+ 
+   /* Only call qsort if there are more than 2 items.  */
+   if (num > 2)
+       qsort (cl->sorted, num, sizeof (partition_pair_p), compare_pairs);
  }
  
  
*************** pop_best_coalesce (coalesce_list_p cl, i
*** 1345,1355 ****
  
    gcc_assert (!cl->add_mode);
  
!   node = cl->list[0];
!   if (!node)
      return NO_BEST_COALESCE;
  
!   cl->list[0] = node->next;
  
    *p1 = node->first_partition;
    *p2 = node->second_partition;
--- 1391,1400 ----
  
    gcc_assert (!cl->add_mode);
  
!   if (cl->num_sorted == 0)
      return NO_BEST_COALESCE;
  
!   node = cl->sorted[--(cl->num_sorted)];
  
    *p1 = node->first_partition;
    *p2 = node->second_partition;
*************** void 
*** 1729,1768 ****
  dump_coalesce_list (FILE *f, coalesce_list_p cl)
  {
    partition_pair_p node;
!   int x, num;
    tree var;
  
    if (cl->add_mode)
      {
        fprintf (f, "Coalesce List:\n");
!       num = num_var_partitions (cl->map);
!       for (x = 0; x < num; x++)
          {
! 	  node = cl->list[x];
! 	  if (node)
! 	    {
! 	      fprintf (f, "[");
! 	      print_generic_expr (f, partition_to_var (cl->map, x), TDF_SLIM);
! 	      fprintf (f, "] - ");
! 	      for ( ; node; node = node->next)
! 	        {
! 		  var = partition_to_var (cl->map, node->second_partition);
! 		  print_generic_expr (f, var, TDF_SLIM);
! 		  fprintf (f, "(%1d), ", node->cost);
! 		}
! 	      fprintf (f, "\n");
! 	    }
  	}
      }
    else
      {
        fprintf (f, "Sorted Coalesce list:\n");
!       for (node = cl->list[0]; node; node = node->next)
          {
  	  fprintf (f, "(%d) ", node->cost);
  	  var = partition_to_var (cl->map, node->first_partition);
  	  print_generic_expr (f, var, TDF_SLIM);
! 	  fprintf (f, " : ");
  	  var = partition_to_var (cl->map, node->second_partition);
  	  print_generic_expr (f, var, TDF_SLIM);
  	  fprintf (f, "\n");
--- 1774,1807 ----
  dump_coalesce_list (FILE *f, coalesce_list_p cl)
  {
    partition_pair_p node;
!   partition_pair_iterator ppi;
!   int x;
    tree var;
  
    if (cl->add_mode)
      {
        fprintf (f, "Coalesce List:\n");
!       FOR_EACH_PARTITION_PAIR (node, ppi, cl)
          {
! 	  tree var1 = partition_to_var (cl->map, node->first_partition);
! 	  tree var2 = partition_to_var (cl->map, node->second_partition);
! 	  print_generic_expr (f, var1, TDF_SLIM);
! 	  fprintf (f, " <-> ");
! 	  print_generic_expr (f, var2, TDF_SLIM);
! 	  fprintf (f, "  (%1d), ", node->cost);
! 	  fprintf (f, "\n");
  	}
      }
    else
      {
        fprintf (f, "Sorted Coalesce list:\n");
!       for (x = cl->num_sorted - 1 ; x >=0; x--)
          {
+ 	  node = cl->sorted[x];
  	  fprintf (f, "(%d) ", node->cost);
  	  var = partition_to_var (cl->map, node->first_partition);
  	  print_generic_expr (f, var, TDF_SLIM);
! 	  fprintf (f, " <-> ");
  	  var = partition_to_var (cl->map, node->second_partition);
  	  print_generic_expr (f, var, TDF_SLIM);
  	  fprintf (f, "\n");
Index: tree-ssa-live.h
===================================================================
*** tree-ssa-live.h	(revision 118519)
--- tree-ssa-live.h	(working copy)
*************** var_to_partition (var_map map, tree var)
*** 147,153 ****
    else
      {
        ann = var_ann (var);
!       if (ann->out_of_ssa_tag)
  	part = VAR_ANN_PARTITION (ann);
        else
          part = NO_PARTITION;
--- 147,153 ----
    else
      {
        ann = var_ann (var);
!       if (ann && ann->out_of_ssa_tag)
  	part = VAR_ANN_PARTITION (ann);
        else
          part = NO_PARTITION;
*************** type_var_decompact (type_var_p tv)
*** 671,701 ****
     all desired information has been collected, the object can be used to 
     order the pairs for processing.  */
  
! /* This structure defines a pair for coalescing.  */
  
! typedef struct partition_pair_d
  {
    int first_partition;
    int second_partition;
    int cost;
!   struct partition_pair_d *next;
! } *partition_pair_p;
  
! /* This structure maintains the list of coalesce pairs.  
!    When add_mode is true, list is a triangular shaped list of coalesce pairs.
!    The smaller partition number is used to index the list, and the larger is
!    index is located in a partition_pair_p object. These lists are sorted from 
!    smallest to largest by 'second_partition'.  New coalesce pairs are allowed
!    to be added in this mode.
!    When add_mode is false, the lists have all been merged into list[0]. The
!    rest of the lists are not used. list[0] is ordered from most desirable
!    coalesce to least desirable. pop_best_coalesce() retrieves the pairs
!    one at a time.  */
  
  typedef struct coalesce_list_d 
  {
    var_map map;
!   partition_pair_p *list;
    bool add_mode;
  } *coalesce_list_p;
  
--- 671,696 ----
     all desired information has been collected, the object can be used to 
     order the pairs for processing.  */
  
! /* This structure defines a pair entry.  */
  
! typedef struct partition_pair
  {
    int first_partition;
    int second_partition;
    int cost;
! } * partition_pair_p;
  
! extern unsigned int partition_pair_map_hash (const void *);
! extern int partition_pair_map_eq (const void *, const void *);
! 
! /* This structure maintains the list of coalesce pairs.  */
  
  typedef struct coalesce_list_d 
  {
    var_map map;
!   htab_t list;
!   partition_pair_p *sorted;
!   int num_sorted;
    bool add_mode;
  } *coalesce_list_p;
  

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]