RFA: GCC 4.2.1: Stabalizing coalesce_list's qsort

[Nick Clifton <nickc at redhat dot com>]

Hi Guys,

  I am not sure if this patch counts as fixing a regression, but I am
  going to submit it anyway.

  The problem is that gcc appears to rely upon the
  sort_coalesce_list() function in tree-ssa-live.c performing a stable
  sort of the coalesce list.  (ie one where items with the same key
  value retain the same relative ordering after the sort).
  Unfortunately the C library function qsort() does not guarantee
  this, and while it just so happens that under Linux the qsort is
  stable, under other operating systems and execution environments
  this is not the case.  (The problem was actually detected when
  running gcc under Cygwin).

  The proposed patch fixes the problem by extending the comparison
  function passed to the invocation of qsort so that when two
  partition pairs do have the same cost they are compared based on
  their location in the partition arrays.  This has the effect of
  stabalizing the sort, allowing the Cygwin hosted toolchain to behave
  in exactly the same way as the Linux hosted toolchain, and so
  preventing Cygwin-only code generation bugs.

  Is this patch suitable for application to the 4.2 branch ?

Cheers
  Nick

gcc/ChangeLog
2007-08-20  Nick Clifton  <nickc@redhat.com>

	* tree-ssa-live.c (compare_pairs): Stabalize the comparison by
	checking the partition indicies if the costs are the same.

Index: gcc/tree-ssa-live.c
===================================================================
--- gcc/tree-ssa-live.c	(revision 127641)
+++ gcc/tree-ssa-live.c	(working copy)
@@ -1261,7 +1261,21 @@ add_coalesce (coalesce_list_p cl, int p1
 static
 int compare_pairs (const void *p1, const void *p2)
 {
-  return (*(partition_pair_p *)p2)->cost - (*(partition_pair_p *)p1)->cost;
+  partition_pair_p * pp1 = (partition_pair_p *) p1;
+  partition_pair_p * pp2 = (partition_pair_p *) p2;
+  int result;
+
+  result = (* pp2)->cost - (* pp1)->cost;
+  /* If the costs are the same, use the partition indicies in order to
+     obtain a stable sort.  Other parts of the SSA code depend upon a
+     stable sort, but qsort does not guarantee this when the primary
+     keys are the same.  */
+  if (result == 0)
+    result = (* pp2)->first_partition - (* pp1)->first_partition;
+  if (result == 0)
+    result = (* pp2)->second_partition - (* pp1)->second_partition;
+
+  return result;
 }