This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
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
>>
>