Re: [RFA][PATCH][PR tree-optimization/64058] Improve and stabilize sorting of coalesce pairs

[Jeff Law <law at redhat dot com>]

On 03/11/2016 03:02 AM, Richard Biener wrote:
[Big snip]

> Can you please split out the 'index' introduction as a separate patch
> and apply that?
> I think it is quite obviously a good idea and might make regression
> hunting easier later if needed.
Done.  Actual patch installed attached for archival purposes.   I'll 
address your comments on the rest of the patch independently.

Jeff

commit 0171eb6090691291571a8db83a5789ecac118e57
Author: law <law@138bc75d-0d04-0410-961f-82ee72b054a4>
Date:   Fri Mar 11 21:07:31 2016 +0000

    	PR tree-optimization/64058
    	* tree-ssa-coalesce.c (struct coalesce_pair): Add new field INDEX.
    	(num_coalesce_pairs): Move up earlier in file.
    	(find_coalesce_pair): Initialize the INDEX field for each pair
    	discovered.
    	(compare_pairs): No longer sort on the elements in each pair.
    	Instead break ties with the index of the coalesce pair.
    
    git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@234149 138bc75d-0d04-0410-961f-82ee72b054a4

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index c69c753..f3a7351 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,13 @@
+2016-03-11  Jeff Law  <law@redhat.com>
+
+	PR tree-optimization/64058
+	* tree-ssa-coalesce.c (struct coalesce_pair): Add new field INDEX.
+	(num_coalesce_pairs): Move up earlier in file.
+	(find_coalesce_pair): Initialize the INDEX field for each pair
+	discovered.
+	(compare_pairs): No longer sort on the elements in each pair.
+	Instead break ties with the index of the coalesce pair.
+
 2016-03-11  Kyrylo Tkachov  <kyrylo.tkachov@arm.com>
 
 	PR target/70002
diff --git a/gcc/tree-ssa-coalesce.c b/gcc/tree-ssa-coalesce.c
index 6624e7e..e49876e 100644
--- a/gcc/tree-ssa-coalesce.c
+++ b/gcc/tree-ssa-coalesce.c
@@ -50,6 +50,11 @@ struct coalesce_pair
   int first_element;
   int second_element;
   int cost;
+
+  /* The order in which coalescing pairs are discovered is recorded in this
+     field, which is used as the final tie breaker when sorting coalesce
+     pairs.  */
+  int index;
 };
 
 /* Coalesce pair hashtable helpers.  */
@@ -254,6 +259,13 @@ delete_coalesce_list (coalesce_list *cl)
   free (cl);
 }
 
+/* Return the number of unique coalesce pairs in CL.  */
+
+static inline int
+num_coalesce_pairs (coalesce_list *cl)
+{
+  return cl->list->elements ();
+}
 
 /* Find a matching coalesce pair object in CL for the pair P1 and P2.  If
    one isn't found, return NULL if CREATE is false, otherwise create a new
@@ -290,6 +302,7 @@ find_coalesce_pair (coalesce_list *cl, int p1, int p2, bool create)
       pair->first_element = p.first_element;
       pair->second_element = p.second_element;
       pair->cost = 0;
+      pair->index = num_coalesce_pairs (cl);
       *slot = pair;
     }
 
@@ -343,29 +356,14 @@ compare_pairs (const void *p1, const void *p2)
   int result;
 
   result = (* pp1)->cost - (* pp2)->cost;
-  /* Since qsort does not guarantee stability we use the elements
-     as a secondary key.  This provides us with independence from
-     the host's implementation of the sorting algorithm.  */
+  /* And if everything else is equal, then sort based on which
+     coalesce pair was found first.  */
   if (result == 0)
-    {
-      result = (* pp2)->first_element - (* pp1)->first_element;
-      if (result == 0)
-	result = (* pp2)->second_element - (* pp1)->second_element;
-    }
+    result = (*pp2)->index - (*pp1)->index;
 
   return result;
 }
 
-
-/* Return the number of unique coalesce pairs in CL.  */
-
-static inline int
-num_coalesce_pairs (coalesce_list *cl)
-{
-  return cl->list->elements ();
-}
-
-
 /* Iterate over CL using ITER, returning values in PAIR.  */
 
 #define FOR_EACH_PARTITION_PAIR(PAIR, ITER, CL)		\