Re: Unstable build/host qsorts causing differing generated target code

[Jeff Law <law at redhat dot com>]

On 01/12/2018 11:26 AM, Cory Fields wrote:
> Quick disclaimer: I'm 100% new to GCC code and the dev process, so
> there are bound to be some faulty assumptions below.
> 
> I recently worked on a build of gcc, x86_64-pc-linux-gnu ->
> x86_64-pc-linux-musl. In order to boost my confidence in musl, I
> decided that I'd like to ensure that 3 (and 4) stage bootstraps
> succeed and compare equal.
> 
> I quickly ran into failed object comparisons at stage3. The issue, as
> it turned out, was that musl's qsort algorithm differs significantly
> from gcc's, though both (as far as I can tell) are perfectly legal.
> The c spec allows for different results in the cast of unstable
> arrays.
THe key here is the results can differ if the comparison function is not
stable.  That's inherent in the qsort algorithms.

But, if the comparison functions are fixed, then the implementation
differences between the qsorts won't matter.

Alexander Monokov has led an effort to identify cases where the
comparison functions do not provide a stable ordering and to fix them.
Some remain, but the majority have been addressed over the last year.
His work also includes a qsort checking implementation to try and spot
these problems as part of GCC's internal consistency checking mechanisms.

His work is on the development trunk and will show up in the upcoming
gcc-8 release.

jeff