| Message ID | 20170715204749.24398-3-amonakov@ispras.ru |
|---|---|
| State | New |
| Headers | show |
On 07/15/2017 02:47 PM, Alexander Monakov wrote: > This qsort comparator lacks anti-commutativity and can indicate > A < B < A if A and B have the same bitpos. Return 0 in that case. > > * gimple-ssa-store-merging.c (sort_by_bitpos): Return 0 on equal bitpos. OK. jeff
On Sat, Jul 15, 2017 at 11:47:45PM +0300, Alexander Monakov wrote: > --- a/gcc/gimple-ssa-store-merging.c > +++ b/gcc/gimple-ssa-store-merging.c > @@ -516,12 +516,12 @@ sort_by_bitpos (const void *x, const void *y) > store_immediate_info *const *tmp = (store_immediate_info * const *) x; > store_immediate_info *const *tmp2 = (store_immediate_info * const *) y; > > - if ((*tmp)->bitpos <= (*tmp2)->bitpos) > + if ((*tmp)->bitpos < (*tmp2)->bitpos) > return -1; > else if ((*tmp)->bitpos > (*tmp2)->bitpos) > return 1; > - > - gcc_unreachable (); > + else > + return 0; > } Does any sort using this comparison function require the sort to be stable? It looks like the <= was simply a typo and should have been <, but the gcc_unreachable was as intended? (With <= it is trivially unreachable there). Segher
On Sat, 22 Jul 2017, Segher Boessenkool wrote: > On Sat, Jul 15, 2017 at 11:47:45PM +0300, Alexander Monakov wrote: > > --- a/gcc/gimple-ssa-store-merging.c > > +++ b/gcc/gimple-ssa-store-merging.c > > @@ -516,12 +516,12 @@ sort_by_bitpos (const void *x, const void *y) > > store_immediate_info *const *tmp = (store_immediate_info * const *) x; > > store_immediate_info *const *tmp2 = (store_immediate_info * const *) y; > > > > - if ((*tmp)->bitpos <= (*tmp2)->bitpos) > > + if ((*tmp)->bitpos < (*tmp2)->bitpos) > > return -1; > > else if ((*tmp)->bitpos > (*tmp2)->bitpos) > > return 1; > > - > > - gcc_unreachable (); > > + else > > + return 0; > > } > > Does any sort using this comparison function require the sort to be > stable? > > It looks like the <= was simply a typo and should have been <, but > the gcc_unreachable was as intended? (With <= it is trivially > unreachable there). I think it's best if the original author can chime in - adding Kyrill. (to be clear, equal bitpos is possible, this issue causes qsort checker errors) Alexander
Hi, On 24/07/17 21:48, Alexander Monakov wrote: > On Sat, 22 Jul 2017, Segher Boessenkool wrote: > >> On Sat, Jul 15, 2017 at 11:47:45PM +0300, Alexander Monakov wrote: >>> --- a/gcc/gimple-ssa-store-merging.c >>> +++ b/gcc/gimple-ssa-store-merging.c >>> @@ -516,12 +516,12 @@ sort_by_bitpos (const void *x, const void *y) >>> store_immediate_info *const *tmp = (store_immediate_info * const *) x; >>> store_immediate_info *const *tmp2 = (store_immediate_info * const *) y; >>> >>> - if ((*tmp)->bitpos <= (*tmp2)->bitpos) >>> + if ((*tmp)->bitpos < (*tmp2)->bitpos) >>> return -1; >>> else if ((*tmp)->bitpos > (*tmp2)->bitpos) >>> return 1; >>> - >>> - gcc_unreachable (); >>> + else >>> + return 0; >>> } >> Does any sort using this comparison function require the sort to be >> stable? >> >> It looks like the <= was simply a typo and should have been <, but >> the gcc_unreachable was as intended? (With <= it is trivially >> unreachable there). > I think it's best if the original author can chime in - adding Kyrill. > > (to be clear, equal bitpos is possible, this issue causes qsort checker errors) For the uses of this function the order when the bitpos is the same does not matter, I just wanted to avoid returning zero to avoid perturbations due to qsort. IMO the right thing to do here to avoid the qsort checker errors is to break the tie between store_immediate_info objects with equal bitpos by using the sort_by_order heuristic i.e. something like "return (*tmp)->order - (*tmp2)->order;". That should give well-behaved results as the order of two store_immediate_info objects is guaranteed not to be the same (otherwise something has gone wrong elsewhere). Thanks, Kyrill > Alexander
On Tue, Jul 25, 2017 at 10:34 AM, Kyrill Tkachov <kyrylo.tkachov@foss.arm.com> wrote: > Hi, > > On 24/07/17 21:48, Alexander Monakov wrote: >> >> On Sat, 22 Jul 2017, Segher Boessenkool wrote: >> >>> On Sat, Jul 15, 2017 at 11:47:45PM +0300, Alexander Monakov wrote: >>>> >>>> --- a/gcc/gimple-ssa-store-merging.c >>>> +++ b/gcc/gimple-ssa-store-merging.c >>>> @@ -516,12 +516,12 @@ sort_by_bitpos (const void *x, const void *y) >>>> store_immediate_info *const *tmp = (store_immediate_info * const *) >>>> x; >>>> store_immediate_info *const *tmp2 = (store_immediate_info * const *) >>>> y; >>>> - if ((*tmp)->bitpos <= (*tmp2)->bitpos) >>>> + if ((*tmp)->bitpos < (*tmp2)->bitpos) >>>> return -1; >>>> else if ((*tmp)->bitpos > (*tmp2)->bitpos) >>>> return 1; >>>> - >>>> - gcc_unreachable (); >>>> + else >>>> + return 0; >>>> } >>> >>> Does any sort using this comparison function require the sort to be >>> stable? >>> >>> It looks like the <= was simply a typo and should have been <, but >>> the gcc_unreachable was as intended? (With <= it is trivially >>> unreachable there). >> >> I think it's best if the original author can chime in - adding Kyrill. >> >> (to be clear, equal bitpos is possible, this issue causes qsort checker >> errors) > > > For the uses of this function the order when the bitpos is the same > does not matter, I just wanted to avoid returning zero to avoid > perturbations > due to qsort. > IMO the right thing to do here to avoid the qsort checker errors is to break > the tie between > store_immediate_info objects with equal bitpos by using the sort_by_order > heuristic > i.e. something like "return (*tmp)->order - (*tmp2)->order;". > That should give well-behaved results as the order of two > store_immediate_info objects > is guaranteed not to be the same (otherwise something has gone wrong > elsewhere). Agreed. Richard. > Thanks, > Kyrill > >> Alexander > >
On Tue, 25 Jul 2017, Kyrill Tkachov wrote: > For the uses of this function the order when the bitpos is the same > does not matter, I just wanted to avoid returning zero to avoid perturbations > due to qsort. But you can't stabilize qsort in that manner, in fact by making the comparator invalid you achieve the opposite: making the output unpredictable, even with respect to elements with different bitpos. > IMO the right thing to do here to avoid the qsort checker errors is to break > the tie between store_immediate_info objects with equal bitpos by using the > sort_by_order heuristic i.e. something like "return (*tmp)->order - > (*tmp2)->order;". That should give well-behaved results as the order of two > store_immediate_info objects is guaranteed not to be the same (otherwise > something has gone wrong elsewhere). Note that my patch in this subthread has been applied already, please submit a separate patch if you want to add this stabilizing clause. Alexander
diff --git a/gcc/gimple-ssa-store-merging.c b/gcc/gimple-ssa-store-merging.c index 64b8351..c99960b 100644 --- a/gcc/gimple-ssa-store-merging.c +++ b/gcc/gimple-ssa-store-merging.c @@ -516,12 +516,12 @@ sort_by_bitpos (const void *x, const void *y) store_immediate_info *const *tmp = (store_immediate_info * const *) x; store_immediate_info *const *tmp2 = (store_immediate_info * const *) y; - if ((*tmp)->bitpos <= (*tmp2)->bitpos) + if ((*tmp)->bitpos < (*tmp2)->bitpos) return -1; else if ((*tmp)->bitpos > (*tmp2)->bitpos) return 1; - - gcc_unreachable (); + else + return 0; } /* Sorting function for store_immediate_info objects.