Re: [PATCH][middle-end] Make qsort in tree-ssa-sccvn.c stable.

[Richard Guenther <richard dot guenther at gmail dot com>]

On Tue, May 12, 2009 at 3:59 AM, Doug Kwan (關振紱) <dougkwan@google.com> wrote:
> This patch stabilizes sort of SSC in tree-ssa-sccvn.c so that sort
> result is not dependent of the implementation of qsort().  Previously,
> instability in sort resuilt caused slightly different code to be
> generated on OSX and Linux hosted gcc compiled for arm-none-eabi.  The
> patch has been bootstrapped and regression tested natively on
> x86_64-unknown-linux-gnu.
>
> Okay to commit?

Splitting this into two functions is confusing.  Also in general
it doesn't make sense to distinguish things further.

I guess you are hitting the PHI node case, in which case I
would suggest to simply do

      if (gimple_code (opstmta) == GIMPLE_PHI
          && gimple_code (opstmtb) == GIMPLE_PHI)
        return SSA_NAME_VERSION (PHI_RESULT (opstmta)) -
SSA_NAME_VERSION (PHI_RESULT (opstmtb));

instead of return 0.

Richard.


> 2009-05-11  Doug Kwan  <dougkwan@google.com>
>
>        * tree-ssa-sccvn.c (compare_ops_1): Renamed from compare_ops.
>        (compare_ops): Wrapper for original compare_ops to stabilize qsort.
>
> Index: gcc/gcc/tree-ssa-sccvn.c
> ===================================================================
> --- gcc/gcc/tree-ssa-sccvn.c    (revision 147396)
> +++ gcc/gcc/tree-ssa-sccvn.c    (working copy)
> @@ -2411,7 +2411,7 @@ visit_use (tree use)
>  /* Compare two operands by reverse postorder index */
>
>  static int
> -compare_ops (const void *pa, const void *pb)
> +compare_ops_1 (const void *pa, const void *pb)
>  {
>   const tree opa = *((const tree *)pa);
>   const tree opb = *((const tree *)pb);
> @@ -2451,6 +2451,36 @@ compare_ops (const void *pa, const void
>   return rpo_numbers[bba->index] - rpo_numbers[bbb->index];
>  }
>
> +static int
> +compare_ops (const void *pa, const void *pb)
> +{
> +  const tree opa = *((const tree *)pa);
> +  const tree opb = *((const tree *)pb);
> +  unsigned HOST_WIDE_INT uid_a, uid_b;
> +  unsigned HOST_WIDE_INT ver_a, ver_b;
> +  int status = compare_ops_1 (pa, pb);
> +
> +  if (status != 0)
> +    return status;
> +
> +  /* Make qsort stable by doing addition comparisons. */
> +  uid_a = DECL_UID (SSA_NAME_VAR (opa));
> +  uid_b = DECL_UID (SSA_NAME_VAR (opb));
> +  if (uid_a < uid_b)
> +    return -1;
> +  else if (uid_a > uid_b)
> +    return 1;
> +
> +  ver_a = SSA_NAME_VERSION (opa);
> +  ver_b = SSA_NAME_VERSION (opb);
> +  if (ver_a < ver_b)
> +    return -1;
> +  else if (ver_a > ver_b)
> +    return 1;
> +  else
> +    return 0;
> +}
> +
>  /* Sort an array containing members of a strongly connected component
>    SCC so that the members are ordered by RPO number.
>    This means that when the sort is complete, iterating through the
>