Re: RFA: GCC 4.2.1: Stabalizing coalesce_list's qsort

["Michael Meissner" <michael dot meissner at amd dot com>]

On Mon, Aug 20, 2007 at 11:34:37AM +0100, Nick Clifton wrote:
> 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

I probably would have written the code as, which saves an extra test in the
case where the comparison is not 0:

  if (result == 0)
    {
      result = (* pp2)->first_partition - (* pp1)->first_partition;
      if (result == 0)
        result = (* pp2)->first_partition - (* pp1)->first_partition;
    }

I will note that GCC has run into the problem of assuming qsort is stable
before (notably the compiler in the 1995 and 2000 versions of SPEC).

> 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;
>  }
> 
> 

-- 
Michael Meissner, AMD
90 Central Street, MS 83-29, Boxborough, MA, 01719, USA
michael.meissner@amd.com