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

[Doug Kwan (關振德)]

I will submit the patch after bootstrapping and regression test.
There was a typo in previous patch unfortunately and that will get
fixed.

-Doug

2009/5/13 Richard Guenther <richard.guenther@gmail.com>:
> On Wed, May 13, 2009 at 9:09 PM, Doug Kwan (關振德) <dougkwan@google.com> wrote:
>> This is not true. Even in trunk, there are non-PHI cases where a
>> GIMPLE statement has multiple operands to be sorted.  I added checking
>> code for that condition and top-of-trunk failed to build libgcc.a due
>> to an asm statement.   The output at the end of this mail shows the
>> offending statments and two operands.  I changed my patch now that it
>> is in one function.
>
> Huh, asms.  Ok...
>
> The modified patch is ok.
>
> Thanks,
> Richard.
>
>> -Doug
>>
>> -- new patch--
>> Index: gcc/gcc/tree-ssa-sccvn.c
>> ===================================================================
>> --- gcc/gcc/tree-ssa-sccvn.c    (revision 147447)
>> +++ gcc/gcc/tree-ssa-sccvn.c    (working copy)
>> @@ -2421,7 +2421,7 @@ compare_ops (const void *pa, const void
>>   basic_block bbb;
>>
>>   if (gimple_nop_p (opstmta) && gimple_nop_p (opstmtb))
>> -    return 0;
>> +    return SSA_NAME_VERSION (opa) - SSA_NAME_VERSION (opb);
>>   else if (gimple_nop_p (opstmta))
>>     return -1;
>>   else if (gimple_nop_p (opstmtb))
>> @@ -2431,7 +2431,7 @@ compare_ops (const void *pa, const void
>>   bbb = gimple_bb (opstmtb);
>>
>>   if (!bba && !bbb)
>> -    return 0;
>> +    return SSA_NAME_VERSION (opa) - SSA_NAME_VERSION (opb);
>>   else if (!bba)
>>     return -1;
>>   else if (!bbb)
>> @@ -2441,12 +2441,15 @@ compare_ops (const void *pa, const void
>>     {
>>       if (gimple_code (opstmta) == GIMPLE_PHI
>>          && gimple_code (opstmtb) == GIMPLE_PHI)
>> -       return 0;
>> +       return SSA_NAME_VERSION (opa) - SSA_NAME_VERSION (opb);
>>       else if (gimple_code (opstmta) == GIMPLE_PHI)
>>        return -1;
>>       else if (gimple_code (opstmtb) == GIMPLE_PHI)
>>        return 1;
>> -      return gimple_uid (opstmta) - gimple_uid (opstmtb);
>> +      else if ((gimple_uid (opstmta) != gimple_uid (opstmtb))
>> +        return gimple_uid (opstmta) - gimple_uid (opstmtb);
>> +      else
>> +       return SSA_NAME_VERSION (opa) - SSA_NAME_VERSION (opb);
>>     }
>>   return rpo_numbers[bba->index] - rpo_numbers[bbb->index];
>>  }
>> ---
>> /disk2/dougkwan/gcc-trunk/obj-2/./gcc/xgcc
>> -B/disk2/dougkwan/gcc-trunk/obj-2/./gcc/
>> -B/usr/local/x86_64-unknown-linux-gnu/bin/
>> -B/usr/local/x86_64-unknown-linux-gnu/lib/ -isystem
>> /usr/local/x86_64-unknown-linux-gnu/include -isystem
>> /usr/local/x86_64-unknown-linux-gnu/sys-include    -g -O2 -m32 -O2  -g
>> -O2 -DIN_GCC   -W -Wall -Wwrite-strings -Wstrict-prototypes
>> -Wmissing-prototypes -Wcast-qual -Wold-style-definition  -isystem
>> ./include  -fPIC -g -DHAVE_GTHR_DEFAULT -DIN_LIBGCC2
>> -D__GCC_FLOAT_NOT_NEEDED   -I. -I. -I../../.././gcc
>> -I../../../../gcc/libgcc -I../../../../gcc/libgcc/.
>> -I../../../../gcc/libgcc/../gcc -I../../../../gcc/libgcc/../include
>> -I../../../../gcc/libgcc/config/libbid -DENABLE_DECIMAL_BID_FORMAT
>> -DHAVE_CC_TLS -DUSE_TLS -Wno-missing-prototypes -Wno-type-limits -o
>> divtf3.o -MT divtf3.o -MD -MP -MF divtf3.dep -fexceptions -c
>> ../../../../gcc/libgcc/../gcc/config/soft-fp/divtf3.c
>> -fvisibility=hidden -DHIDE_EXPORTS
>> # .MEM_889 = VDEF <.MEM_888>
>> __asm__("mul{l} %3" : "=a" _t_350, "=d" _m_f[2] : "%0" D.1739_348 :
>> "rm" D.1622_349);
>>
>> _t_350
>> .MEM_889
>> ../../../../gcc/libgcc/../gcc/config/soft-fp/divtf3.c: In function '__divtf3':
>> ../../../../gcc/libgcc/../gcc/config/soft-fp/divtf3.c:35: internal
>> compiler error: in compare_ops, at tree-ssa-sccvn.c:2464
>> Please submit a full bug report,
>> with preprocessed source if appropriate.
>> See <http://gcc.gnu.org/bugs.html> for instructions.
>>
>>
>>
>> 2009/5/13 Richard Guenther <richard.guenther@gmail.com>:
>>>
>>> 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.
>>
>