Implement coalesce list with hash table instead of linked list.

	* 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.




git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@119378 138bc75d-0d04-0410-961f-82ee72b054a4

1 files changed, 12 insertions, 17 deletions

diff --git a/gcc/tree-ssa-live.h b/gcc/tree-ssa-live.h
index f0c59028e19..17ada27bda7 100644
--- a/gcc/tree-ssa-live.h
+++ b/gcc/tree-ssa-live.h
@@ -147,7 +147,7 @@ var_to_partition (var_map map, tree var)
   else
     {
       ann = var_ann (var);
-      if (ann->out_of_ssa_tag)
+      if (ann && ann->out_of_ssa_tag)
 	part = VAR_ANN_PARTITION (ann);
       else
         part = NO_PARTITION;
@@ -671,31 +671,26 @@ type_var_decompact (type_var_p tv)
    all desired information has been collected, the object can be used to 
    order the pairs for processing.  */
 
-/* This structure defines a pair for coalescing.  */
+/* This structure defines a pair entry.  */
 
-typedef struct partition_pair_d
+typedef struct partition_pair
 {
   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.  */
+} * 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;
-  partition_pair_p *list;
+  htab_t list;
+  partition_pair_p *sorted;
+  int num_sorted;
   bool add_mode;
 } *coalesce_list_p;