Re: Linux and Windows generate different binaries

[Segher Boessenkool]

On Mon, Jul 17, 2017 at 11:10:01AM +0300, Alexander Monakov wrote:
> On Sun, 16 Jul 2017, Segher Boessenkool wrote:
> > > How? There's no stable sort in libc and switching over to std::stable_sort
> > > would be problematic.
> > 
> > Why?
> 
> - you'd need to decide if the build time cost of extra 8000+ lines
>   lines brought in by  (per each TU) is acceptable;
> 
> - you'd need to decide if the code size cost of multiple instantiations
>   of template stable_sort is acceptable (or take measures to unify them);

OTOH it should be faster than calling callbacks all the time.

> - you'd need to adapt comparators, as STL uses a different interface
>   that C qsort;
> 
> - you'd need to ensure it doesn't lead to a noticeable slowdown.

Okay, so the slowness of compiling STL stuff is a very real issue.

> > Sure.  Some of our sorts in fact require stable sort though
> 
> At moment only bb-reorder appears to use std::stable_sort, is that what
> you meant, or are there more places?

For example all_saved_regs (in caller-save.c) ensures a stable sort
(I don't know if it actually needs it, or this is just to ensure
only identical objects compare equal).  I know the one in bb-reorder
very much does need it (I added it myself).  Sure, you can avoid it
by essentially doing it manually (with a last-resort comparison).


Segher

Re: Linux and Windows generate different binaries

[Alexander Monakov]

On Sun, 16 Jul 2017, Segher Boessenkool wrote:
> > How? There's no stable sort in libc and switching over to std::stable_sort
> > would be problematic.
> 
> Why?

- you'd need to decide if the build time cost of extra 8000+ lines
  lines brought in by  (per each TU) is acceptable;

- you'd need to decide if the code size cost of multiple instantiations
  of template stable_sort is acceptable (or take measures to unify them);

- you'd need to adapt comparators, as STL uses a different interface
  that C qsort;

- you'd need to ensure it doesn't lead to a noticeable slowdown.

(unrelated, but calls to std::stable sort cannot be intercepted by Yuri's
sortcheck, and of course my recent sortcheck-like patch entirely missed it too)

> Sure.  Some of our sorts in fact require stable sort though

At moment only bb-reorder appears to use std::stable_sort, is that what
you meant, or are there more places?

Alexander

Re: Linux and Windows generate different binaries

[Oleg Endo]

On Sun, 2017-07-16 at 17:32 -0500, Segher Boessenkool wrote:
> On Sun, Jul 16, 2017 at 11:54:43PM +0300, Alexander Monakov wrote:
> > 
> > On Sun, 16 Jul 2017, Segher Boessenkool wrote:
> > > 
> > > I am well aware, and that is not what I asked.  If we would use
> > > stable sorts everywhere

> > How? There's no stable sort in libc and switching over to
> > std::stable_sort would be problematic.

> Why?

Actually GCC has been carrying around its very own implementation of
sort algorithms in libstdc++.  It's just not being used for the
compiler itself.  Because before GCC was compiled as C, using them was
impossible.  But now that it's compiled as C++, why not just use the
algos from GCC's libstdc++?

Cheers,
Oleg

Re: Linux and Windows generate different binaries

[Segher Boessenkool]

On Sun, Jul 16, 2017 at 11:54:43PM +0300, Alexander Monakov wrote:
> On Sun, 16 Jul 2017, Segher Boessenkool wrote:
> > I am well aware, and that is not what I asked.  If we would use stable
> > sorts everywhere
> 
> How? There's no stable sort in libc and switching over to std::stable_sort
> would be problematic.

Why?

> The obvious approach is adding an implementation of
> a stable sort in GCC, but at that point it doesn't matter if it's stable,
> the fact it's deterministic is sufficient for reproducibility.

Sure.  Some of our sorts in fact require stable sort though, so if we
do not use that everywhere people will still have to decide whether it
is required in a specific case or not.

> > we would not have to think about whether some sorting routine has to be
> > stable or if we can get away with a (slightly slower) non-stable sort.
> 
> I think you mean '(slightly faster)'.

Yes I do, whoops :-)

> > That is just a plain bug, undefined behaviour even (C11 7.22.5/4).
> > Of course it needs to be fixed.
> 
> I've posted patches towards this goal.

Thanks!


Segher

Re: Linux and Windows generate different binaries

[Alexander Monakov]

On Sun, 16 Jul 2017, Segher Boessenkool wrote:
> I am well aware, and that is not what I asked.  If we would use stable
> sorts everywhere

How? There's no stable sort in libc and switching over to std::stable_sort
would be problematic. The obvious approach is adding an implementation of
a stable sort in GCC, but at that point it doesn't matter if it's stable,
the fact it's deterministic is sufficient for reproducibility.

> we would not have to think about whether some sorting routine has to be
> stable or if we can get away with a (slightly slower) non-stable sort.

I think you mean '(slightly faster)'.

> That is just a plain bug, undefined behaviour even (C11 7.22.5/4).
> Of course it needs to be fixed.

I've posted patches towards this goal.

Alexander

Re: Linux and Windows generate different binaries

[Segher Boessenkool]

On Sun, Jul 16, 2017 at 12:38:58PM +0300, Alexander Monakov wrote:
> On Sat, 15 Jul 2017, Segher Boessenkool wrote:
> > Would it hurt us to use stable sorts *everywhere*?
> 
> Stability (using the usual definition: keeping the original order of
> elements that compare equal) is not required to achieve reproducibility [*].

I am well aware, and that is not what I asked.  If we would use stable
sorts everywhere we would not have to think about whether some sorting
routine has to be stable or if we can get away with a (slightly slower)
non-stable sort.

> [*] nor would it be sufficient, given our current practice of passing
> invalid comparators to libc sort, at which point anything can happen
> due to undefined behavior

That is just a plain bug, undefined behaviour even (C11 7.22.5/4).
Of course it needs to be fixed.


Segher

Re: Linux and Windows generate different binaries

[Alexander Monakov]

On Sat, 15 Jul 2017, Segher Boessenkool wrote:
> Would it hurt us to use stable sorts *everywhere*?

Stability (using the usual definition: keeping the original order of
elements that compare equal) is not required to achieve reproducibility [*].
GCC could import or nih any non-randomized implementation of a [potentially
not stable, e.g. qsort] sorting routine, and that would be sufficient
to eliminate this source of codegen differences.

Alexander

[*] nor would it be sufficient, given our current practice of passing
invalid comparators to libc sort, at which point anything can happen
due to undefined behavior

Re: Linux and Windows generate different binaries

[Yuri Gribov]

On Sat, Jul 15, 2017 at 10:01 PM, Alexander Monakov  wrote:
> On Fri, 14 Jul 2017, Yuri Gribov wrote:
>> I've also detect transitiveness violation compare_assert_loc
>> (tree-vrp.c), will send fix once tests are done.
>
> There are more issues still, see the thread starting at
> https://gcc.gnu.org/ml/gcc-patches/2017-07/msg00899.html

Nice!

I've also reproduced some of these bugs (tree-vrp.c and
gimple-ssa-store-merging.c). But these are transitiveness errors
whereas this thread is mainly about unstable sorts so I didn't report
them here.

-Y

Re: Linux and Windows generate different binaries

[Alexander Monakov]

On Fri, 14 Jul 2017, Yuri Gribov wrote:
> I've also detect transitiveness violation compare_assert_loc
> (tree-vrp.c), will send fix once tests are done.

There are more issues still, see the thread starting at
https://gcc.gnu.org/ml/gcc-patches/2017-07/msg00899.html

Alexander

Re: Linux and Windows generate different binaries

[Segher Boessenkool]

On Sat, Jul 15, 2017 at 07:40:13PM +0100, Yuri Gribov wrote:
> Looked at generators, we have three comparison routines which return 0
> for different objects but all seem to be safe i.e. can't influence
> code generated by GCC.
> 
> alt_state_cmp (genautomata.c) - intentional, duplicates are removed 
> afterwards.
> 
> optab_rcode_cmp (genopinit.c) - compares objects with rcode == UNKNOWN
> as equal but that's fine as later codes treats them in the same way
> (sets their code_to_optab_ table to unknown_optab).
> 
> subroutine_candidate_cmp (genrecog.c) - this compares function
> candidates with same number of statements in them as equal. This may
> cause different split of state recognition code to recog_%d
> subroutines but should not change semantics of code as a whole.

That sounds like a debugging nightmare though.

Would it hurt us to use stable sorts *everywhere*?


Segher

Re: Linux and Windows generate different binaries

[Yuri Gribov]

On Fri, Jul 14, 2017 at 8:45 AM, Yuri Gribov  wrote:
> FWIW I've done a quick analysis of recent gcc source code using
> https://github.com/yugr/sortcheck and found lots of comparison
> functions which can return 0 for different objects.
>
> All these may cause arrays to be sorted differently on different
> platforms but it's not immediately clear whether this may cause actual
> difference in generated code.
>
> Here's a list for cc1 (I can analyze other executables e.g. generators
> and cc1plus if needed).

Looked at generators, we have three comparison routines which return 0
for different objects but all seem to be safe i.e. can't influence
code generated by GCC.

alt_state_cmp (genautomata.c) - intentional, duplicates are removed afterwards.

optab_rcode_cmp (genopinit.c) - compares objects with rcode == UNKNOWN
as equal but that's fine as later codes treats them in the same way
(sets their code_to_optab_ table to unknown_optab).

subroutine_candidate_cmp (genrecog.c) - this compares function
candidates with same number of statements in them as equal. This may
cause different split of state recognition code to recog_%d
subroutines but should not change semantics of code as a whole.

-Y

Re: Linux and Windows generate different binaries

[Yuri Gribov]

On Thu, Jul 13, 2017 at 4:56 AM, Klaus Kruse Pedersen (Klaus)
 wrote:
> On Wed, 2017-07-12 at 08:57 -0600, Sandra Loosemore wrote:
>> On 07/12/2017 05:07 AM, Klaus Kruse Pedersen (Klaus) wrote:
>> > I have seen reproducible builds being discussed here, but what is
>> > the
>> > position on inter c-lib and OS reproducible builds?
>>
>> I think we consider unstable sort problems bugs and have fixed them
>> in
>> the past.  Bugzilla search turned up #28964 and I remember at least
>> one
>> more recent instance of this as well (although not the details any
>> more).
>
>
> Yes, 28964 is similar to the issue I was hit by.
>
> By extension, does that mean that all qsort compare/rank functions that
> can return 0, should be considered buggy?
>
> I went through a some of the 140'ish rank functions - and it does
> indeed look like considerable effort went into returning only +1 and
> -1.
>
> A general pattern seem to be:
>
> return da ? 1 : -1;
>
> And comments like:
>
>   /* If regs are equally good, sort by their numbers, so that the
>  results of qsort leave nothing to chance.  */
>
>
> But there are exceptions, all rank functions in
>
> tree-ssa-loop-ivopts.c,
> tree-ssa-loop-niter.c
> tree-ssa-loop-im.c
>
> can return 0.

FWIW I've done a quick analysis of recent gcc source code using
https://github.com/yugr/sortcheck and found lots of comparison
functions which can return 0 for different objects.

All these may cause arrays to be sorted differently on different
platforms but it's not immediately clear whether this may cause actual
difference in generated code.

Here's a list for cc1 (I can analyze other executables e.g. generators
and cc1plus if needed).

allocno_hard_regs_compare (ira-color.c) - sorts registers according to
their spill cost.

compare_access_positions (tree-sra.c) - accesses to same var in
different statements may be compared equal e.g.
  (gdb) p debug_gimple_stmt((**(access_p *)prev).stmt)
  # VUSE <.MEM_6(D)>
  _1 = s_7(D)->b;
  $6 = void
  (gdb) p debug_gimple_stmt((**(access_p *)val).stmt)
  # .MEM_11 = VDEF <.MEM_10>
  s_7(D)->b = 0B;
  $7 = void

sort_bbs_in_loop_postorder_cmp (tree-ssa-loop-im.c) - basic blocks
sorted according to loop in which they occur.

sort_locs_in_loop_postorder_cmp (tree-ssa-loop-im.c) - ditto for memrefs.

group_compare_offset (tree-ssa-loop-ivopts.c) - accesses in different
statements may be compared equal e.g.
  (gdb) cal debug_gimple_stmt((**(struct iv_use **)prev).stmt)
  # .MEM_626 = VDEF <.MEM_346>
  adpm[i_313] = adpm[_24];
  (gdb) cal debug_gimple_stmt((**(struct iv_use **)val).stmt)
  # .MEM_627 = VDEF <.MEM_626>
  adpm[i_313].next = _25;

common_cand_cmp (tree-ssa-loop-ivopts.c) - sorts IV candidates based
on number of uses.

object_range_compare_func (ira-build.c) - compares equal for different
subregs of the same registers e.g.
  (gdb) p **(ira_object_t *)val
  $4 = {allocno = 0x80, conflicts_array = 0x20, live_ranges =
0x7614e180, subword = -169917888, conflicts_array_size = 32767,
  id = -160201072, min = 32767, max = -169985296, conflict_hard_regs =
{0, 0}, total_conflict_hard_regs = {0, 0},
  num_accumulated_conflicts = 0, conflict_vec_p = 0}
  (gdb) p **(ira_object_t *)prev
  $5 = {allocno = 0x80, conflicts_array = 0x20, live_ranges =
0x7614e180, subword = -166434272, conflicts_array_size = 32767,
  id = -160201072, min = 32767, max = -169985776, conflict_hard_regs =
{0, 0}, total_conflict_hard_regs = {0, 0},
  num_accumulated_conflicts = 0, conflict_vec_p = 0}

compare_address_parts (loop-invariant.c) - sorts rtx based on operator
precedence.

I've also detect transitiveness violation compare_assert_loc
(tree-vrp.c), will send fix once tests are done.

-Y

Re: Linux and Windows generate different binaries

[Yuri Gribov]

On Thu, Jul 13, 2017 at 4:56 AM, Klaus Kruse Pedersen (Klaus)
 wrote:
> On Wed, 2017-07-12 at 08:57 -0600, Sandra Loosemore wrote:
>> On 07/12/2017 05:07 AM, Klaus Kruse Pedersen (Klaus) wrote:
>> > I have seen reproducible builds being discussed here, but what is
>> > the
>> > position on inter c-lib and OS reproducible builds?
>>
>> I think we consider unstable sort problems bugs and have fixed them
>> in
>> the past.  Bugzilla search turned up #28964 and I remember at least
>> one
>> more recent instance of this as well (although not the details any
>> more).
>
>
> Yes, 28964 is similar to the issue I was hit by.
>
> By extension, does that mean that all qsort compare/rank functions that
> can return 0, should be considered buggy?
>
> I went through a some of the 140'ish rank functions - and it does
> indeed look like considerable effort went into returning only +1 and
> -1.
>
> A general pattern seem to be:
>
> return da ? 1 : -1;
>
> And comments like:
>
>   /* If regs are equally good, sort by their numbers, so that the
>  results of qsort leave nothing to chance.  */
>
>
> But there are exceptions, all rank functions in
>
> tree-ssa-loop-ivopts.c,
> tree-ssa-loop-niter.c
> tree-ssa-loop-im.c
>
> can return 0.

One more issue with some of qsort callbacks is that they do not always
satisfy ordering axioms which in practice may result in random
variations in output. I once reported this in
https://gcc.gnu.org/ml/gcc-patches/2015-12/msg02141.html but didn't
follow up.

-Y

Re: Linux and Windows generate different binaries

[Klaus Kruse Pedersen (Klaus)]

On Wed, 2017-07-12 at 08:57 -0600, Sandra Loosemore wrote:
> On 07/12/2017 05:07 AM, Klaus Kruse Pedersen (Klaus) wrote:
> > I have seen reproducible builds being discussed here, but what is
> > the
> > position on inter c-lib and OS reproducible builds?
> 
> I think we consider unstable sort problems bugs and have fixed them
> in 
> the past.  Bugzilla search turned up #28964 and I remember at least
> one 
> more recent instance of this as well (although not the details any
> more).


Yes, 28964 is similar to the issue I was hit by.

By extension, does that mean that all qsort compare/rank functions that
can return 0, should be considered buggy?

I went through a some of the 140'ish rank functions - and it does
indeed look like considerable effort went into returning only +1 and
-1.

A general pattern seem to be:

return da ? 1 : -1;

And comments like:

  /* If regs are equally good, sort by their numbers, so that the
 results of qsort leave nothing to chance.  */


But there are exceptions, all rank functions in

tree-ssa-loop-ivopts.c,
tree-ssa-loop-niter.c
tree-ssa-loop-im.c

can return 0.




> 
> -Sandra
> 

Re: Linux and Windows generate different binaries

[Ramana Radhakrishnan]

On Wed, Jul 12, 2017 at 3:57 PM, Sandra Loosemore
 wrote:
> On 07/12/2017 05:07 AM, Klaus Kruse Pedersen (Klaus) wrote:
>>
>> I have seen reproducible builds being discussed here, but what is the
>> position on inter c-lib and OS reproducible builds?
>
>
> I think we consider unstable sort problems bugs and have fixed them in the
> past.  Bugzilla search turned up #28964 and I remember at least one more
> recent instance of this as well (although not the details any more).

https://gcc.gnu.org/ml/gcc-patches/2015-11/msg02444.html

>
> -Sandra
>

Re: Linux and Windows generate different binaries

[Sandra Loosemore]

On 07/12/2017 05:07 AM, Klaus Kruse Pedersen (Klaus) wrote:

I have seen reproducible builds being discussed here, but what is the
position on inter c-lib and OS reproducible builds?


I think we consider unstable sort problems bugs and have fixed them in 
the past.  Bugzilla search turned up #28964 and I remember at least one 
more recent instance of this as well (although not the details any more).


-Sandra