This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
RFA: GCC 4.2.1: Stabalizing coalesce_list's qsort
- From: Nick Clifton <nickc at redhat dot com>
- To: gcc-patches at gcc dot gnu dot org
- Date: Mon, 20 Aug 2007 11:34:37 +0100
- Subject: RFA: GCC 4.2.1: Stabalizing coalesce_list's qsort
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;
}