On Thu, Jul 13, 2017 at 4:56 AM, Klaus Kruse Pedersen (Klaus) <klauskpeder...@rdamicro.com> 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 = 0x7ffff614e180, 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 = 0x7ffff614e180, 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
