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

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

2009/5/12 Doug Kwan (關振紱) <dougkwan@google.com>:
> Your suggested fix does not work.  In one case, compare_ops return 0
> because both operands are memory tags from the same gimple statement.
> I can add SSA-version check in all plase that the original code can
> return 0.

Ok, in addition to the PHI case you will need (on 4.4 branch only, trunk
should be fine with only the PHI case fixed)

     else if (opstmta == opstmtb)
        return SSA_NAME_VERSION (opa) - SSA_NAME_VERSION (opb);
     return gimple_uid (opstmta) - gimple_uid (opstmtb);

thus, in case we look at the same defining stmts defer to the definition.

That should hopefully also fix it for 4.4.  On trunk we have at most
one memory tag per stmt, so that situation cannot appear there.

Richard.

> -Doug
>
> --------------------------
> 2493      const tree opa = *((const tree *)pa);
> (gdb) n
> 2494      const tree opb = *((const tree *)pb);
> (gdb)
> 2495      gimple opstmta = SSA_NAME_DEF_STMT (opa);
> (gdb)
> 2496      gimple opstmtb = SSA_NAME_DEF_STMT (opb);
> (gdb)
> 2500      if (gimple_nop_p (opstmta) && gimple_nop_p (opstmtb))
> (gdb) call debug_gimple_stmt(opstmta)
> # sSuperShapeObjects_29 = VDEF <sSuperShapeObjects_15>
> # sGroundPlane_30 = VDEF <sGroundPlane_17>
> # SMT.242_31 = VDEF <SMT.242_19>
> # SMT.243_32 = VDEF <SMT.243_21>
> # SMT.244_33 = VDEF <SMT.244_23> { sSuperShapeObjects sGroundPlane
> SMT.242 SMT.243 SMT.244 }
> free (D.4241_8);
>
> (gdb) call debug_gimple_stmt(opstmtb)
> # sSuperShapeObjects_29 = VDEF <sSuperShapeObjects_15>
> # sGroundPlane_30 = VDEF <sGroundPlane_17>
> # SMT.242_31 = VDEF <SMT.242_19>
> # SMT.243_32 = VDEF <SMT.243_21>
> # SMT.244_33 = VDEF <SMT.244_23> { sSuperShapeObjects sGroundPlane
> SMT.242 SMT.243 SMT.244 }
> free (D.4241_8);
>
> (gdb) n
> 2502      else if (gimple_nop_p (opstmta))
> (gdb)
> 2504      else if (gimple_nop_p (opstmtb))
> (gdb)
> 2507      bba = gimple_bb (opstmta);
> (gdb)
> 2508      bbb = gimple_bb (opstmtb);
> (gdb)
> 2510      if (!bba && !bbb)
> (gdb)
> 2512      else if (!bba)
> (gdb)
> 2514      else if (!bbb)
> (gdb)
> 2517      if (bba == bbb)
> (gdb)
> 2519          if (gimple_code (opstmta) == GIMPLE_PHI
> (gdb)
> 2522          else if (gimple_code (opstmta) == GIMPLE_PHI)
> (gdb)
> 2524          else if (gimple_code (opstmtb) == GIMPLE_PHI)
> (gdb)
> 2526          return gimple_uid (opstmta) - gimple_uid (opstmtb);
>
>
> 2009/5/12 Richard Guenther <richard.guenther@gmail.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
>>>
>>
>