RE: RFA: GCC 4.2.1: Stabalizing coalesce_list's qsort

[Andrew MacLeod <amacleod at redhat dot com>]

On Wed, 2007-08-22 at 13:16 -0400, Meissner, Michael wrote:
> > -----Original Message-----

> > I presume there was a legitimate bug under the covers tho?  the
> unstable
> > sort by itself should still result in correct code being generated...
> 
> Generally in these types of situations it will cause the compiler to
> select different items that have the same weighting.  It can make
> tracking down bugs much harder, because different people debugging it
> will get different behaviors depending on what system they are using.
> As I said, this has already come up in the past, and we fixed it in the
> register allocation by making the sort stable by comparing the indices.
> 
> I would vote for having patches like Nick suggested applied to 4.2.x as
> well as the mainline.

I tended to agree in a different branch of this thread... Either don't
use an unstable sort like qsort, or pay the compile time cost for the
extra compares. For 4.2 its certainly less disruptive from a code
standpoint to apply the patch, but I wonder how much turmoil it might
cause in generated code. It will significantly change the coalesce order
on all architectures, which may result in quite different code being
generated. That would be my biggest concern at this point.   

I'm considering alternatives for mainline which take into account that
there may be many elements with the same cost, and perhaps we can
actually sort a lot less.  It still doesn't preclude this patch being
applied in the meantime. Since 4.3 isn't a released compiler, I wouldn't
worry about the coalesce ordering so much, especially since the
algorithm changed a bit anyway.

Andrew