This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

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


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.

-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 (w) <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
>>
>


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]