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

[Michael Matz <matz at suse dot de>]

Hi,

On Tue, 12 May 2009, Rafael Espindola wrote:

> > + Â/* Make qsort stable by doing addition comparisons. */
> 
> s/addition/additional/  ?
> 
> 
> > +
> > + Â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;
> > +}
> 
> If this function returns 0 then the sort not stable,

The comparison routine must return 0 when the two inputs are actually the 
same entity.  This is the case for two SSA names that have the same 
version (they aren't just equal, they are really the same pointer).  The 
above requirement makes a difference for some qsort implementations that 
needlessly call the comparison function also on the same array elements; 
these are _very_ confused if the comparison then doesn't return 0.

Unstability is only given when the comparison returns 0 for any other 
cases besides pointer equality.  It could have been recoded by an a priori 
check for pa==pb, in which case it could be replaced by an 
gcc_unreachable, which indeed might be more clear.


Ciao,
Michael.