[PATCH 0/6] qsort comparator consistency fixes

[PATCH 0/6] qsort comparator consistency fixes

[Alexander Monakov]

Hello,

(previous thread here:
https://gcc.gnu.org/ml/gcc-patches/2016-07/msg00944.html )

we still have a few places in GCC where the comparator function passed to qsort
is not actually a proper sorting predicate.  Most commonly it fails to impose
total ordering by lacking transitivity.  It's useful to fix such instances,
because:

- such comparators don't work as intended;
- they lead to issues that can only be reproduced with a specific libc;
- failure usually happens not in qsort, but quite some time later.

(PR 71702 and its duplicates is a good highlight for the latter two, it
could only be observed with qsort from musl libc and manifested as assert
failure in the vectorizer, which was not trivial to diagnose)

The goal of this patchset is to introduce automatic comparator consistency
verification in GCC, with zero impact on release-checking compilers and
minimal workflow disturbance (it should be possible to easily suppress
checking to e.g. unblock bootstrap when there's no obvious fix).

Changes from the last year's patch:

+ both vec::qsort and libc ::qsort are checked (previously only vec::)
+ individual callers can opt out of checking
+ a bit more sensible cutoff for avoiding O(n^2) time complexity
+ unlike a year ago, now this needs 5 accompanying patches for broken
  comparators, meaning new issues have crept in

The first question last year from Richard was about bootstrap time impact.
Last year it appeared to be in the noise, I can do it again if there's
interest.

Patches 1-3 fix broken comparators where the fix is evident, patches 4-5
avoid qsort checking where comparators needs nontrivial fixes, and patch
6 is the actual checking implementation.

  tree-vrp: fix compare_assert_loc qsort comparator
  gimple-ssa-store-merging.c: fix sort_by_bitpos
  lra-assigns.c: fix pseudo_compare_func
  lra-assigns.c: give up on qsort checking in assign_by_spills
  haifa-sched.c: give up qsort checking when autoprefetch heuristic is
    in use
  qsort comparator consistency checking

 gcc/genmodes.c                 |  2 +-
 gcc/gimple-ssa-store-merging.c |  6 +--
 gcc/haifa-sched.c              |  8 ++++
 gcc/lra-assigns.c              | 10 ++---
 gcc/system.h                   | 11 +++++
 gcc/tree-vrp.c                 |  2 +-
 gcc/vec.c                      | 95 ++++++++++++++++++++++++++++++++++++++++++
 7 files changed, 124 insertions(+), 10 deletions(-)

-- 
1.8.3.1

[PATCH 3/6] lra-assigns.c: fix pseudo_compare_func

[Alexander Monakov]

This comparator lacks anti-commutativity and can indicate
A < B < A if both A and B satisfy non_spilled_static_chain_regno_p.
Proceed to following tie-breakers in that case.

(it looks like the code incorrectly assumes that at most one register
in the array will satisfy non_spilled_static_chain_regno_p)

	* lra-assigns.c (pseudo_compare_func): Fix comparison step based on
        non_spilled_static_chain_regno_p.
---
 gcc/lra-assigns.c | 7 +++----
 1 file changed, 3 insertions(+), 4 deletions(-)

diff --git a/gcc/lra-assigns.c b/gcc/lra-assigns.c
index 42556d3..2aadeef 100644
--- a/gcc/lra-assigns.c
+++ b/gcc/lra-assigns.c
@@ -253,10 +253,9 @@ pseudo_compare_func (const void *v1p, const void *v2p)
 
   /* Assign hard reg to static chain pointer first pseudo when
      non-local goto is used.  */
-  if (non_spilled_static_chain_regno_p (r1))
-    return -1;
-  else if (non_spilled_static_chain_regno_p (r2))
-    return 1;
+  if ((diff = (non_spilled_static_chain_regno_p (r2)
+	       - non_spilled_static_chain_regno_p (r1))) != 0)
+    return diff;
 
   /* Prefer to assign more frequently used registers first.  */
   if ((diff = lra_reg_info[r2].freq - lra_reg_info[r1].freq) != 0)
-- 
1.8.3.1

Re: [PATCH 3/6] lra-assigns.c: fix pseudo_compare_func

[Jeff Law]

On 07/15/2017 02:47 PM, Alexander Monakov wrote:
> This comparator lacks anti-commutativity and can indicate
> A < B < A if both A and B satisfy non_spilled_static_chain_regno_p.
> Proceed to following tie-breakers in that case.
> 
> (it looks like the code incorrectly assumes that at most one register
> in the array will satisfy non_spilled_static_chain_regno_p)
> 
> 	* lra-assigns.c (pseudo_compare_func): Fix comparison step based on
>         non_spilled_static_chain_regno_p.
OK.
jeff

[PATCH 5/6] haifa-sched.c: give up qsort checking when autoprefetch heuristic is in use

[Alexander Monakov]

The autopref_rank_for_schedule sub-comparator and its subroutine
autopref_rank_data lack transitivity.  Skip checking if they are in use.

This heuristic is disabled by default everywhere except ARM and AArch64,
so on other targets this does not suppress  checking all the time.

	* haifa-sched.c (ready_sort_real): Disable qsort checking if
        autoprefetch heuristic will be used.
        (autopref_rank_for_schedule): Add FIXME.
---
 gcc/haifa-sched.c | 8 ++++++++
 1 file changed, 8 insertions(+)

diff --git a/gcc/haifa-sched.c b/gcc/haifa-sched.c
index af0ed27..71ad3c4 100644
--- a/gcc/haifa-sched.c
+++ b/gcc/haifa-sched.c
@@ -3081,11 +3081,18 @@ ready_sort_real (struct ready_list *ready)
   if (sched_verbose >= 4)
     stats1 = rank_for_schedule_stats;
 
+  /* autopref_rank_for_schedule lacks transitivity.  */
+  if (PARAM_VALUE (PARAM_SCHED_AUTOPREF_QUEUE_DEPTH) >= 0)
+    qsort_disable_checking |= 1;
+
   if (n_ready_real == 2)
     swap_sort (first, n_ready_real);
   else if (n_ready_real > 2)
     qsort (first, n_ready_real, sizeof (rtx), rank_for_schedule);
 
+  if (PARAM_VALUE (PARAM_SCHED_AUTOPREF_QUEUE_DEPTH) >= 0)
+    qsort_disable_checking &= ~1;
+
   if (sched_verbose >= 4)
     {
       rank_for_schedule_stats_diff (&stats1, &rank_for_schedule_stats);
@@ -5704,6 +5711,7 @@ autopref_rank_data (autopref_multipass_data_t data1,
 }
 
 /* Helper function for rank_for_schedule sorting.  */
+/* FIXME: this comparator lacks transitivity and is thus invalid for qsort.  */
 static int
 autopref_rank_for_schedule (const rtx_insn *insn1, const rtx_insn *insn2)
 {
-- 
1.8.3.1

Re: [PATCH 5/6] haifa-sched.c: give up qsort checking when autoprefetch heuristic is in use

[Jeff Law]

On 07/15/2017 02:47 PM, Alexander Monakov wrote:
> The autopref_rank_for_schedule sub-comparator and its subroutine
> autopref_rank_data lack transitivity.  Skip checking if they are in use.
> 
> This heuristic is disabled by default everywhere except ARM and AArch64,
> so on other targets this does not suppress  checking all the time.
> 
> 	* haifa-sched.c (ready_sort_real): Disable qsort checking if
>         autoprefetch heuristic will be used.
>         (autopref_rank_for_schedule): Add FIXME.
This is also OK once the final patch for consistency checking is approved.

jeff

[PATCH 2/6] gimple-ssa-store-merging.c: fix sort_by_bitpos

[Alexander Monakov]

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.
---
 gcc/gimple-ssa-store-merging.c | 6 +++---
 1 file changed, 3 insertions(+), 3 deletions(-)

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.
-- 
1.8.3.1

Re: [PATCH 2/6] gimple-ssa-store-merging.c: fix sort_by_bitpos

[Jeff Law]

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

Re: [PATCH 2/6] gimple-ssa-store-merging.c: fix sort_by_bitpos

[Segher Boessenkool]

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

Re: [PATCH 2/6] gimple-ssa-store-merging.c: fix sort_by_bitpos

[Alexander Monakov]

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

Re: [PATCH 2/6] gimple-ssa-store-merging.c: fix sort_by_bitpos

[Kyrill Tkachov]

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

Re: [PATCH 2/6] gimple-ssa-store-merging.c: fix sort_by_bitpos

[Richard Biener]

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
>
>

Re: [PATCH 2/6] gimple-ssa-store-merging.c: fix sort_by_bitpos

[Alexander Monakov]

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

[PATCH 1/6] tree-vrp: fix compare_assert_loc qsort comparator

[Alexander Monakov]

Subtracting values to produce a -/0/+ comparison value only works when
original values have limited range.  Otherwise it leads to broken
comparator that indicates 0 < 0x40000000 < 0x80000000 < 0.

Yuri posted an equivalent patch just a few hours ago:
https://gcc.gnu.org/ml/gcc-patches/2017-07/msg00882.html

	* tree-vrp.c (compare_assert_loc): Properly compare hash values.
---
 gcc/tree-vrp.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
index 28205f1..d1888f6 100644
--- a/gcc/tree-vrp.c
+++ b/gcc/tree-vrp.c
@@ -6459,7 +6459,7 @@ compare_assert_loc (const void *pa, const void *pb)
     return (a->e != NULL
 	    ? a->e->src->index - b->e->src->index
 	    : a->bb->index - b->bb->index);
-  return ha - hb;
+  return ha < hb ? -1 : 1;
 }
 
 /* Process all the insertions registered for every name N_i registered
-- 
1.8.3.1

Re: [PATCH 1/6] tree-vrp: fix compare_assert_loc qsort comparator

[Jeff Law]

On 07/15/2017 02:47 PM, Alexander Monakov wrote:
> Subtracting values to produce a -/0/+ comparison value only works when
> original values have limited range.  Otherwise it leads to broken
> comparator that indicates 0 < 0x40000000 < 0x80000000 < 0.
> 
> Yuri posted an equivalent patch just a few hours ago:
> https://gcc.gnu.org/ml/gcc-patches/2017-07/msg00882.html
> 
> 	* tree-vrp.c (compare_assert_loc): Properly compare hash values.
Richi already ack'd Yuri's version, so let's stick with that.

jeff

[PATCH 4/6] lra-assigns.c: give up on qsort checking in assign_by_spills

[Alexander Monakov]

The reload_pseudo_compare_func comparator, when used from assign_by_spills,
can be non-transitive, indicating A < B < C < A if both A and C satisfy
!bitmap_bit_p (&non_reload_pseudos, rAC), but B does not.

This function was originally a proper comparator, and the problematic
clause was added to fix PR 57878:
https://gcc.gnu.org/ml/gcc-patches/2013-07/msg00732.html

That the comparator is invalid implies that that PR, if it still exists,
can reappear (but probably under more complicated circumstances).

This looks like a sensitive area, so disabling checking is the only
obvious approach.

	* lra-assigns.c (reload_pseudo_compare_func): Add a FIXME.
        (assign_by_spills): Use non-checking qsort.
---
 gcc/lra-assigns.c | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)

diff --git a/gcc/lra-assigns.c b/gcc/lra-assigns.c
index 2aadeef..a67d1a6 100644
--- a/gcc/lra-assigns.c
+++ b/gcc/lra-assigns.c
@@ -217,6 +217,7 @@ reload_pseudo_compare_func (const void *v1p, const void *v2p)
       /* The code below executes rarely as nregs == 1 in most cases.
 	 So we should not worry about using faster data structures to
 	 check reload pseudos.  */
+      /* FIXME this makes comparator non-transitive and thus invalid.  */
       && ! bitmap_bit_p (&non_reload_pseudos, r1)
       && ! bitmap_bit_p (&non_reload_pseudos, r2))
     return diff;
@@ -1384,7 +1385,7 @@ assign_by_spills (void)
   bitmap_ior_into (&non_reload_pseudos, &lra_optional_reload_pseudos);
   for (iter = 0; iter <= 1; iter++)
     {
-      qsort (sorted_pseudos, n, sizeof (int), reload_pseudo_compare_func);
+      qsort_nochk (sorted_pseudos, n, sizeof (int), reload_pseudo_compare_func);
       nfails = 0;
       for (i = 0; i < n; i++)
 	{
-- 
1.8.3.1

Re: [PATCH 4/6] lra-assigns.c: give up on qsort checking in assign_by_spills

[Yuri Gribov]

On Sat, Jul 15, 2017 at 9:47 PM, Alexander Monakov <amonakov@ispras.ru> wrote:
> The reload_pseudo_compare_func comparator, when used from assign_by_spills,
> can be non-transitive, indicating A < B < C < A if both A and C satisfy
> !bitmap_bit_p (&non_reload_pseudos, rAC), but B does not.
>
> This function was originally a proper comparator, and the problematic
> clause was added to fix PR 57878:
> https://gcc.gnu.org/ml/gcc-patches/2013-07/msg00732.html
>
> That the comparator is invalid implies that that PR, if it still exists,
> can reappear (but probably under more complicated circumstances).
>
> This looks like a sensitive area, so disabling checking is the only
> obvious approach.

May make sense to add PR rtl-optimization/68988 annotation to changelog.

>         * lra-assigns.c (reload_pseudo_compare_func): Add a FIXME.
>         (assign_by_spills): Use non-checking qsort.
> ---
>  gcc/lra-assigns.c | 3 ++-
>  1 file changed, 2 insertions(+), 1 deletion(-)
>
> diff --git a/gcc/lra-assigns.c b/gcc/lra-assigns.c
> index 2aadeef..a67d1a6 100644
> --- a/gcc/lra-assigns.c
> +++ b/gcc/lra-assigns.c
> @@ -217,6 +217,7 @@ reload_pseudo_compare_func (const void *v1p, const void *v2p)
>        /* The code below executes rarely as nregs == 1 in most cases.
>          So we should not worry about using faster data structures to
>          check reload pseudos.  */
> +      /* FIXME this makes comparator non-transitive and thus invalid.  */
>        && ! bitmap_bit_p (&non_reload_pseudos, r1)
>        && ! bitmap_bit_p (&non_reload_pseudos, r2))
>      return diff;
> @@ -1384,7 +1385,7 @@ assign_by_spills (void)
>    bitmap_ior_into (&non_reload_pseudos, &lra_optional_reload_pseudos);
>    for (iter = 0; iter <= 1; iter++)
>      {
> -      qsort (sorted_pseudos, n, sizeof (int), reload_pseudo_compare_func);
> +      qsort_nochk (sorted_pseudos, n, sizeof (int), reload_pseudo_compare_func);
>        nfails = 0;
>        for (i = 0; i < n; i++)
>         {
> --
> 1.8.3.1
>

Re: [PATCH 4/6] lra-assigns.c: give up on qsort checking in assign_by_spills

[Jeff Law]

On 07/15/2017 02:47 PM, Alexander Monakov wrote:
> The reload_pseudo_compare_func comparator, when used from assign_by_spills,
> can be non-transitive, indicating A < B < C < A if both A and C satisfy
> !bitmap_bit_p (&non_reload_pseudos, rAC), but B does not.
> 
> This function was originally a proper comparator, and the problematic
> clause was added to fix PR 57878:
> https://gcc.gnu.org/ml/gcc-patches/2013-07/msg00732.html
> 
> That the comparator is invalid implies that that PR, if it still exists,
> can reappear (but probably under more complicated circumstances).
> 
> This looks like a sensitive area, so disabling checking is the only
> obvious approach.
> 
> 	* lra-assigns.c (reload_pseudo_compare_func): Add a FIXME.
>         (assign_by_spills): Use non-checking qsort.
This is OK once the final comparator consistency checking patch is approved.

jeff

[PATCH 6/6] qsort comparator consistency checking

[Alexander Monakov]

This is the updated qsort comparator verifier.

Since we have vec::qsort(cmp), the patch uses the macro argument counting
trick to redirect only the four-argument invocations of qsort to qsort_chk.
I realize that won't win much sympathies, but a patch doing mass-renaming
of qsort in the whole GCC codebase would win even fewer, I suspect.

The macro ENABLE_FULL_QSORT_CHECKING could be used to enable full O(n^2)
checking, but there's no accompanying configure.ac change.  I'm not sure
that would be useful in practice, so I'd rather turn it into #if 0.

The suppression in genmodes was needed because it's not linked with vec.o.

	* genmodes.c (calc_wider_mode): Suppress qsort macro.
        * system.h [CHECKING_P] (qsort): Redirect to qsort_chk.
        (qsort_nochk): New macro.
        (qsort_chk): Declare.
        (qsort_disable_checking): Declare.
        * vec.c (qsort_chk_error): New static function.
        (qsort_disable_checking): Define.
        (qsort_chk): New function.
---
 gcc/genmodes.c |  2 +-
 gcc/system.h   | 11 +++++++
 gcc/vec.c      | 95 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 107 insertions(+), 1 deletion(-)

diff --git a/gcc/genmodes.c b/gcc/genmodes.c
index f7eaeef..01a0e65 100644
--- a/gcc/genmodes.c
+++ b/gcc/genmodes.c
@@ -880,7 +880,7 @@ calc_wider_mode (void)
 	  for (i = 0, m = modes[c]; m; i++, m = m->next)
 	    sortbuf[i] = m;
 
-	  qsort (sortbuf, i, sizeof (struct mode_data *), cmp_modes);
+	  (qsort) (sortbuf, i, sizeof (struct mode_data *), cmp_modes);
 
 	  sortbuf[i] = 0;
 	  for (j = 0; j < i; j++)
diff --git a/gcc/system.h b/gcc/system.h
index b091794..0f44942 100644
--- a/gcc/system.h
+++ b/gcc/system.h
@@ -1170,4 +1170,15 @@ helper_const_non_const_cast (const char *p)
 /* Get definitions of HOST_WIDE_INT.  */
 #include "hwint.h"
 
+/* qsort comparator consistency checking machinery.  */
+#if CHECKING_P
+/* Except in release-checking compilers, redirect 4-argument qsort calls.  */
+#undef qsort
+#define _5th(_1, _2, _3, _4, _5, ...) _5
+#define qsort(...) _5th (__VA_ARGS__, qsort_chk, 3, 2, qsort, 0) (__VA_ARGS__)
+#endif
+#define qsort_nochk (qsort)
+void qsort_chk (void *, size_t, size_t, int (*)(const void *, const void *));
+extern unsigned qsort_disable_checking;
+
 #endif /* ! GCC_SYSTEM_H */
diff --git a/gcc/vec.c b/gcc/vec.c
index d612703..5d9f1e9 100644
--- a/gcc/vec.c
+++ b/gcc/vec.c
@@ -31,6 +31,12 @@ along with GCC; see the file COPYING3.  If not see
 #include "coretypes.h"
 #include "hash-table.h"
 #include "selftest.h"
+#ifdef GENERATOR_FILE
+#include "errors.h"
+#else
+#include "input.h"
+#include "diagnostic-core.h"
+#endif
 
 /* vNULL is an empty type with a template cast operation that returns
    a zero-initialized vec<T, A, L> instance.  Use this when you want
@@ -42,6 +48,95 @@ along with GCC; see the file COPYING3.  If not see
    they cannot have ctors/dtors.  */
 vnull vNULL;
 
+/* Report qsort comparator CMP consistency check failure with P1, P2, P3 as
+   witness elements.  */
+ATTRIBUTE_NORETURN ATTRIBUTE_COLD
+static void
+qsort_chk_error (const void *p1, const void *p2, const void *p3,
+		 int (*cmp) (const void *, const void *))
+{
+  if (!p3)
+    {
+      int r1 = cmp (p1, p2), r2 = cmp (p2, p1);
+      error ("qsort comparator not anti-commutative: %d, %d", r1, r2);
+    }
+  else if (p1 == p2)
+    {
+      int r = cmp (p1, p3);
+      error ("qsort comparator non-negative on sorted output: %d", r);
+    }
+  else
+    {
+      int r1 = cmp (p1, p2), r2 = cmp (p2, p3), r3 = cmp (p1, p3);
+      error ("qsort comparator not transitive: %d, %d, %d", r1, r2, r3);
+    }
+  internal_error ("qsort checking failed");
+}
+
+unsigned qsort_disable_checking;
+
+/* Wrapper around qsort with checking that CMP is consistent on given input.
+
+   Strictly speaking, passing invalid (non-transitive, non-anti-commutative)
+   comparators to libc qsort can result in undefined behavior.  Therefore we
+   should ideally perform consistency checks prior to invoking qsort, but in
+   order to do that optimally we'd need to sort the array ourselves beforehand
+   with a sorting routine known to be "safe".  Instead, we expect that most
+   implementations in practice will still produce some permutation of input
+   array even for invalid comparators, which enables us to perform checks on
+   the output array.  */
+void
+qsort_chk (void *base, size_t n, size_t size,
+	   int (*cmp)(const void *, const void *))
+{
+  if (!CHECKING_P || qsort_disable_checking)
+    return (qsort) (base, n, size, cmp);
+  (qsort) (base, n, size, cmp);
+#ifdef ENABLE_FULL_QSORT_CHECKING
+#define LIM(n) (n)
+#else
+  /* Limit overall time complexity to O(n log n).  */
+#define LIM(n) ((n) <= 16 ? (n) : 12 + floor_log2 (n))
+#endif
+#define ELT(i) ((const char *) base + (i) * size)
+#define CMP(i, j) cmp (ELT (i), ELT (j))
+#define ERR2(i, j) qsort_chk_error (ELT (i), ELT (j), NULL, cmp)
+#define ERR3(i, j, k) qsort_chk_error (ELT (i), ELT (j), ELT (k), cmp)
+  size_t i1, i2, i, j;
+  /* This outer loop iterates over maximum spans [i1, i2) such that
+     elements within each span compare equal to each other.  */
+  for (i1 = 0; i1 < n; i1 = i2)
+    {
+      /* Position i2 one past last element that compares equal to i1'th.  */
+      for (i2 = i1 + 1; i2 < n; i2++)
+	if (CMP (i1, i2))
+	  break;
+	else if (CMP (i2, i1))
+	  return ERR2 (i1, i2);
+      size_t lim1 = LIM (i2 - i1), lim2 = LIM (n - i2);
+      /* Verify that other pairs within current span compare equal.  */
+      for (i = i1 + 1; i + 1 < i2; i++)
+	for (j = i + 1; j < i1 + lim1; j++)
+	  if (CMP (i, j))
+	    return ERR3 (i, i1, j);
+	  else if (CMP (j, i))
+	    return ERR2 (i, j);
+      /* Verify that elements within this span compare less than
+         elements beyond the span.  */
+      for (i = i1; i < i2; i++)
+	for (j = i2; j < i2 + lim2; j++)
+	  if (CMP (i, j) >= 0)
+	    return ERR3 (i, i1, j);
+	  else if (CMP (j, i) <= 0)
+	    return ERR2 (i, j);
+    }
+#undef ERR3
+#undef ERR2
+#undef CMP
+#undef ELT
+#undef LIM
+}
+
 /* Vector memory usage.  */
 struct vec_usage: public mem_usage
 {
-- 
1.8.3.1

Re: [PATCH 6/6] qsort comparator consistency checking

[Jeff Law]

On 07/15/2017 02:47 PM, Alexander Monakov wrote:
> This is the updated qsort comparator verifier.
> 
> Since we have vec::qsort(cmp), the patch uses the macro argument counting
> trick to redirect only the four-argument invocations of qsort to qsort_chk.
> I realize that won't win much sympathies, but a patch doing mass-renaming
> of qsort in the whole GCC codebase would win even fewer, I suspect.
> 
> The macro ENABLE_FULL_QSORT_CHECKING could be used to enable full O(n^2)
> checking, but there's no accompanying configure.ac change.  I'm not sure
> that would be useful in practice, so I'd rather turn it into #if 0.
> 
> The suppression in genmodes was needed because it's not linked with vec.o.
> 
> 	* genmodes.c (calc_wider_mode): Suppress qsort macro.
>         * system.h [CHECKING_P] (qsort): Redirect to qsort_chk.
>         (qsort_nochk): New macro.
>         (qsort_chk): Declare.
>         (qsort_disable_checking): Declare.
>         * vec.c (qsort_chk_error): New static function.
>         (qsort_disable_checking): Define.
>         (qsort_chk): New function.
I  must have missed something.  Can't you just define

qsort (BASE, NMEMB, SIZE, COMPARE) into

qsort_chk (BASE, NMEMB, SIZE, COMPARE)

That shouldn't affect the qsort from vec?  Right?  Or am I missing something

Jeff

Re: [PATCH 6/6] qsort comparator consistency checking

[Alexander Monakov]

On Mon, 31 Jul 2017, Jeff Law wrote:
> I  must have missed something.  Can't you just define
> 
> qsort (BASE, NMEMB, SIZE, COMPARE) into
> 
> qsort_chk (BASE, NMEMB, SIZE, COMPARE)
> 
> That shouldn't affect the qsort from vec?  Right?  Or am I missing something

If you do

  #define qsort(base, n, sz, cmp) qsort_chk (base, n, sz, cmp)

then all invocations of vec::qsort, i.e.

  myvec.qsort (mycmp);

will yield a preprocessing error due to wrong number of arguments supplied
to the qsort macro (one instead of four).

Alexander

Re: [PATCH 6/6] qsort comparator consistency checking

[Jeff Law]

On 07/31/2017 12:27 PM, Alexander Monakov wrote:
> On Mon, 31 Jul 2017, Jeff Law wrote:
>> I  must have missed something.  Can't you just define
>>
>> qsort (BASE, NMEMB, SIZE, COMPARE) into
>>
>> qsort_chk (BASE, NMEMB, SIZE, COMPARE)
>>
>> That shouldn't affect the qsort from vec?  Right?  Or am I missing something
> 
> If you do
> 
>   #define qsort(base, n, sz, cmp) qsort_chk (base, n, sz, cmp)
> 
> then all invocations of vec::qsort, i.e.
> 
>   myvec.qsort (mycmp);
> 
> will yield a preprocessing error due to wrong number of arguments supplied
> to the qsort macro (one instead of four).
Duh.  Hit me with a clue stick. I guess I have to get familiar with the
macro argument counting trick :-)

jeff

Re: [PATCH 6/6] qsort comparator consistency checking

[Jeff Law]

On 07/15/2017 02:47 PM, Alexander Monakov wrote:
> This is the updated qsort comparator verifier.
> 
> Since we have vec::qsort(cmp), the patch uses the macro argument counting
> trick to redirect only the four-argument invocations of qsort to qsort_chk.
> I realize that won't win much sympathies, but a patch doing mass-renaming
> of qsort in the whole GCC codebase would win even fewer, I suspect.
> 
> The macro ENABLE_FULL_QSORT_CHECKING could be used to enable full O(n^2)
> checking, but there's no accompanying configure.ac change.  I'm not sure
> that would be useful in practice, so I'd rather turn it into #if 0.
> 
> The suppression in genmodes was needed because it's not linked with vec.o.
> 
> 	* genmodes.c (calc_wider_mode): Suppress qsort macro.
>         * system.h [CHECKING_P] (qsort): Redirect to qsort_chk.
>         (qsort_nochk): New macro.
>         (qsort_chk): Declare.
>         (qsort_disable_checking): Declare.
>         * vec.c (qsort_chk_error): New static function.
>         (qsort_disable_checking): Define.
>         (qsort_chk): New function.
Well, there's not *that* many qsort calls.  My quick grep shows 94 and
its a very mechanical change.  Then a poison in system.h to ensure raw
calls to qsort don't return.

The counting trick is, well, ugly.  There's also issues in that some
compilers don't properly implement the C99 pre-processor standard
properly (MSVC) and what happens when there's no arguments?  While not
likely an issue here, I think it highlights that this kind of
preprocessor hackery is just a bad idea.

I'd prefer to just bite the bullet and do the mechanical qsort change.

Jeff

Re: [PATCH 6/6] qsort comparator consistency checking

[Alexander Monakov]

On Wed, 2 Aug 2017, Jeff Law wrote:
> Well, there's not *that* many qsort calls.  My quick grep shows 94 and
> its a very mechanical change.  Then a poison in system.h to ensure raw
> calls to qsort don't return.

Any suggestion for the non-poisoned replacement?  xqsort?  gcc_qsort?

Can you review the rest (the substantial functionality) of the patch
without waiting for the mass-renaming change?

Thanks.
Alexander

Re: [PATCH 6/6] qsort comparator consistency checking

[Jeff Law]

On 08/02/2017 12:00 PM, Alexander Monakov wrote:
> On Wed, 2 Aug 2017, Jeff Law wrote:
>> Well, there's not *that* many qsort calls.  My quick grep shows 94 and
>> its a very mechanical change.  Then a poison in system.h to ensure raw
>> calls to qsort don't return.
> 
> Any suggestion for the non-poisoned replacement?  xqsort?  gcc_qsort?
qsort_chk/qsort_nochk for checked and non-checked?

> 
> Can you review the rest (the substantial functionality) of the patch
> without waiting for the mass-renaming change?
I think the rest is good as-is.  If we find a need to adjust the
checking intervals, then we can do that as a follow-up.

jeff

Re: [PATCH 6/6] qsort comparator consistency checking

[Alexander Monakov]

On Wed, 2 Aug 2017, Jeff Law wrote:
> >> Well, there's not *that* many qsort calls.  My quick grep shows 94 and
> >> its a very mechanical change.  Then a poison in system.h to ensure raw
> >> calls to qsort don't return.

Note that poisoning qsort outlaws vec::qsort too; it would need to be mass-
renamed as well (to vec::sort, presumably).  It seems there are 83 or more
calls to vec::qsort.

> > Any suggestion for the non-poisoned replacement?  xqsort?  gcc_qsort?
> qsort_chk/qsort_nochk for checked and non-checked?

I believe qsort_chk isn't appropriate, checking is not explicitly a part
of interface, and we never use _chk in potentially-checking tree and RTL
accessors either.

Thanks.
Alexander

Re: [PATCH 6/6] qsort comparator consistency checking

[Jeff Law]

On 08/03/2017 08:24 AM, Alexander Monakov wrote:
> On Wed, 2 Aug 2017, Jeff Law wrote:
>>>> Well, there's not *that* many qsort calls.  My quick grep shows 94 and
>>>> its a very mechanical change.  Then a poison in system.h to ensure raw
>>>> calls to qsort don't return.
> 
> Note that poisoning qsort outlaws vec::qsort too; it would need to be mass-
> renamed as well (to vec::sort, presumably).  It seems there are 83 or more
> calls to vec::qsort.
Ugh :(  That's an unfortunate implementation of poisoning :(  Consider a
patch to rename those too pre-approved.


> 
>>> Any suggestion for the non-poisoned replacement?  xqsort?  gcc_qsort?
>> qsort_chk/qsort_nochk for checked and non-checked?
> 
> I believe qsort_chk isn't appropriate, checking is not explicitly a part
> of interface, and we never use _chk in potentially-checking tree and RTL
> accessors either.
How about just "sort"?
Jeff

Re: [PATCH 6/6] qsort comparator consistency checking

[Jakub Jelinek]

On Thu, Aug 03, 2017 at 09:33:13AM -0600, Jeff Law wrote:
> On 08/03/2017 08:24 AM, Alexander Monakov wrote:
> > On Wed, 2 Aug 2017, Jeff Law wrote:
> >>>> Well, there's not *that* many qsort calls.  My quick grep shows 94 and
> >>>> its a very mechanical change.  Then a poison in system.h to ensure raw
> >>>> calls to qsort don't return.
> > 
> > Note that poisoning qsort outlaws vec::qsort too; it would need to be mass-
> > renamed as well (to vec::sort, presumably).  It seems there are 83 or more
> > calls to vec::qsort.
> Ugh :(  That's an unfortunate implementation of poisoning :(  Consider a
> patch to rename those too pre-approved.

Do we really need to rename and poison anything?  qsort () in the source is
something that is most obvious to developers, so trying to force them to use
something different will just mean extra thing to learn.

I mean, isn't it better to just add a static inline qsort that in the
checking case calls qsort_chk, or do the redirection using GNU asm
redirection:
typeof (qsort) __asm ("qsort_chk");
and define extern "C" qsort_chk somewhere?
configure could test whether it works on the target (it wouldn't perhaps
on targets which already use some inline for qsort in their headers or use
qsort as a macro (but the latter wouldn't work anyway with GCC already)).
The _5th macro isn't that bad either, appart from using reserved namespace
identifiers (it really should be something like qsort_5th and the arguments
shouldn't start with underscores).

	Jakub

Re: [PATCH 6/6] qsort comparator consistency checking

[Alexander Monakov]

On Thu, 3 Aug 2017, Jakub Jelinek wrote:
> Do we really need to rename and poison anything?  qsort () in the source is
> something that is most obvious to developers, so trying to force them to use
> something different will just mean extra thing to learn.

Yep, I'd prefer to have a solution that keeps C-style qsort invocations as-is.

Note that with vec::qsort -> vec::sort renaming (which should be less
controversial, STL also has std::vector<T>::sort), the argument counting
trick won't be needed, the redirection will simply be:

  #undef qsort
  #define qsort(base, n, sz, cmp) qsort_chk (base, n, sz, cmp)

> I mean, isn't it better to just add a static inline qsort that in the
> checking case calls qsort_chk,

(redefining qsort like that is formally UB, I'd like to avoid it)

> or do the redirection using GNU asm redirection:
> typeof (qsort) __asm ("qsort_chk");
> and define extern "C" qsort_chk somewhere?
> configure could test whether it works on the target (it wouldn't perhaps
> on targets which already use some inline for qsort in their headers or use
> qsort as a macro (but the latter wouldn't work anyway with GCC already)).

I'd rather not go this way.

> The _5th macro isn't that bad either, appart from using reserved namespace
> identifiers (it really should be something like qsort_5th and the arguments
> shouldn't start with underscores).

I didn't understand what Jeff found "ugly" about it; I wonder what epithets
would be applied then to more, ahem, unusual parts of GCC.

Thanks.
Alexander

Re: [PATCH 6/6] qsort comparator consistency checking

[Oleg Endo]

On Thu, 2017-08-03 at 19:23 +0300, Alexander Monakov wrote:
> 
> Note that with vec::qsort -> vec::sort renaming (which should be less
> controversial, STL also has std::vector<T>::sort)

No it doesn't?  One uses std::sort from <algorithm> on a pair of random
access iterators to sort a std::vector.

Cheers,
Oleg

Re: [PATCH 6/6] qsort comparator consistency checking

[Alexander Monakov]

[-- Attachment #1: Type: text/plain, Size: 379 bytes --]

On Fri, 4 Aug 2017, Oleg Endo wrote:
> > Note that with vec::qsort -> vec::sort renaming (which should be less
> > controversial, STL also has std::vector<T>::sort)
> 
> No it doesn't?  One uses std::sort from <algorithm> on a pair of random
> access iterators to sort a std::vector.

My mistake, but the main point remains: STL uses 'sort' without the 'q'.

Thanks.
Alexander

Re: [PATCH 6/6] qsort comparator consistency checking

[Oleg Endo]

On Thu, 2017-08-03 at 19:31 +0300, Alexander Monakov wrote:
> 
> My mistake, but the main point remains: STL uses 'sort' without the
> 'q'.

I think it'd be better if GCC's custom containers somewhat tried to
follow C++ standard container idioms.  Chopping off the 'q' is one step
towards it.

Cheers,
Oleg

Re: [PATCH 6/6] qsort comparator consistency checking

[Jakub Jelinek]

On Thu, Aug 03, 2017 at 07:23:31PM +0300, Alexander Monakov wrote:
> On Thu, 3 Aug 2017, Jakub Jelinek wrote:
> > Do we really need to rename and poison anything?  qsort () in the source is
> > something that is most obvious to developers, so trying to force them to use
> > something different will just mean extra thing to learn.
> 
> Yep, I'd prefer to have a solution that keeps C-style qsort invocations as-is.
> 
> Note that with vec::qsort -> vec::sort renaming (which should be less
> controversial, STL also has std::vector<T>::sort), the argument counting

vec::qsort -> vec::sort renaming is fine with me.

	Jakub

Re: [PATCH 6/6] qsort comparator consistency checking

[Pedro Alves]

On 08/03/2017 05:23 PM, Alexander Monakov wrote:
> Note that with vec::qsort -> vec::sort renaming (which should be less
> controversial, STL also has std::vector<T>::sort), the argument counting
> trick won't be needed, the redirection will simply be:

OTOH, std::sort's comparison function callback has a different
interface from qsort's.  std::sort wants less-than true/false,
while qsort wants -1/0/1.  Might be less confusing to
leave "sort" for a method that follows std::sort's interface.

You could also consider using std::sort, btw.  I don't think
there's a reason it can't work with vec.  Since std::sort is
a template, the inlining + indirection avoidance often results
in faster sorts (potentially at the expense of compile time).
Consistency checking could be implemented by adding a a gcc::sort
wrapper around std::sort (and calling the former throughout).

Thanks,
Pedro Alves

Re: [PATCH 6/6] qsort comparator consistency checking

[Jeff Law]

On 08/03/2017 10:23 AM, Alexander Monakov wrote:
> On Thu, 3 Aug 2017, Jakub Jelinek wrote:
>> Do we really need to rename and poison anything?  qsort () in the source is
>> something that is most obvious to developers, so trying to force them to use
>> something different will just mean extra thing to learn.
> 
> Yep, I'd prefer to have a solution that keeps C-style qsort invocations as-is.
Revisiting, I'm in agreement with you.

> 
>> The _5th macro isn't that bad either, appart from using reserved namespace
>> identifiers (it really should be something like qsort_5th and the arguments
>> shouldn't start with underscores).
> 
> I didn't understand what Jeff found "ugly" about it; I wonder what epithets
> would be applied then to more, ahem, unusual parts of GCC.
I doubt anyone would want to hear what I might say about other code.
I'm sure I wouldn't want my kids reading how I might refer to certain
parts of GCC.

jeff

Re: [PATCH 6/6] qsort comparator consistency checking

[Alexander Monakov]

On Wed, 9 Aug 2017, Jeff Law wrote:
> >> The _5th macro isn't that bad either, appart from using reserved namespace
> >> identifiers (it really should be something like qsort_5th and the arguments
> >> shouldn't start with underscores).
> > 
> > I didn't understand what Jeff found "ugly" about it; I wonder what epithets
> > would be applied then to more, ahem, unusual parts of GCC.
> I doubt anyone would want to hear what I might say about other code.
> I'm sure I wouldn't want my kids reading how I might refer to certain
> parts of GCC.

Imho it's no good to just say "ugly" in patch review without any further
elaboration, it only serves to provide a minor chilling effect, telling
the contributor they haven't done good enough (for your personal taste)
without informing them where/how they could have improved.

More importantly, am I correct in understanding that at this point all
remaining changes are reviewed and approved, and I can go ahead with
preparing vec::qsort -> vec::sort mass-renaming patch and rebasing the
others on top of it?  Or is the original approach with argument-counting
trick still under consideration?

Thanks.
Alexander

Re: [PATCH 6/6] qsort comparator consistency checking

[Jeff Law]

On 08/10/2017 05:24 AM, Alexander Monakov wrote:
> On Wed, 9 Aug 2017, Jeff Law wrote:
>>>> The _5th macro isn't that bad either, appart from using reserved namespace
>>>> identifiers (it really should be something like qsort_5th and the arguments
>>>> shouldn't start with underscores).
>>>
>>> I didn't understand what Jeff found "ugly" about it; I wonder what epithets
>>> would be applied then to more, ahem, unusual parts of GCC.
>> I doubt anyone would want to hear what I might say about other code.
>> I'm sure I wouldn't want my kids reading how I might refer to certain
>> parts of GCC.
> 
> Imho it's no good to just say "ugly" in patch review without any further
> elaboration, it only serves to provide a minor chilling effect, telling
> the contributor they haven't done good enough (for your personal taste)
> without informing them where/how they could have improved.
> 
> More importantly, am I correct in understanding that at this point all
> remaining changes are reviewed and approved, and I can go ahead with
> preparing vec::qsort -> vec::sort mass-renaming patch and rebasing the
> others on top of it?  Or is the original approach with argument-counting
> trick still under consideration?
I still don't like the argument-counting trick.  But avoiding it seems
even more painful.  So let's go with your original approach with the
argument-counting trick.  At least it's buried and folks likely won't
have to look at it with any regularity.

jeff

Re: [PATCH 6/6] qsort comparator consistency checking

[Jeff Law]

On 08/03/2017 09:52 AM, Jakub Jelinek wrote:
> On Thu, Aug 03, 2017 at 09:33:13AM -0600, Jeff Law wrote:
>> On 08/03/2017 08:24 AM, Alexander Monakov wrote:
>>> On Wed, 2 Aug 2017, Jeff Law wrote:
>>>>>> Well, there's not *that* many qsort calls.  My quick grep shows 94 and
>>>>>> its a very mechanical change.  Then a poison in system.h to ensure raw
>>>>>> calls to qsort don't return.
>>>
>>> Note that poisoning qsort outlaws vec::qsort too; it would need to be mass-
>>> renamed as well (to vec::sort, presumably).  It seems there are 83 or more
>>> calls to vec::qsort.
>> Ugh :(  That's an unfortunate implementation of poisoning :(  Consider a
>> patch to rename those too pre-approved.
> 
> Do we really need to rename and poison anything?  qsort () in the source is
> something that is most obvious to developers, so trying to force them to use
> something different will just mean extra thing to learn.
Thinking about this again, you're probably right.   I failed to
distinguish between this case and something like malloc.  For qsort, if
we're using the numbering hack, introduction of a new qsort call will
result in a qsort call that is properly checked.  In contrast we simply
don't want folks calling malloc & friends directly under any circumstances.

Sorry for taking everyone down a bogus path here.

Jeff

[PATCH 7/6] fortran: fix pair_cmp qsort comparator

[Alexander Monakov]

Hello,

The final tie-breaker in pair_cmp comparator looks strange, it correctly
yields zero for equal expr->symtree-n.sym values, but for unequal values
it produces 0 or 1.  This would be correct for C++ STL-style comparators
that require "less-than" predicate to be computed, but not for C qsort.

The comment before the function seems to confirm that the intent was to
indeed sort in ascending gfc_symbol order, but the code is doing mostly
the opposite.

Make the comparator properly anti-commutative by returning -1 in the last
tie-breaker when appropriate.

Bootstrapped and regtested on x86-64, OK for trunk?

	* interface.c (pair_cmp): Fix gfc_symbol comparison.  Adjust comment.
---
 gcc/fortran/interface.c | 4 +++-
 1 file changed, 3 insertions(+), 1 deletion(-)

diff --git a/gcc/fortran/interface.c b/gcc/fortran/interface.c
index 6fe0647..13e2bdd 100644
--- a/gcc/fortran/interface.c
+++ b/gcc/fortran/interface.c
@@ -3294,7 +3294,7 @@ argpair;
    order:
     - p->a->expr == NULL
     - p->a->expr->expr_type != EXPR_VARIABLE
-    - growing p->a->expr->symbol.  */
+    - by gfc_symbol pointer value (larger first).  */
 
 static int
 pair_cmp (const void *p1, const void *p2)
@@ -3320,6 +3320,8 @@ pair_cmp (const void *p1, const void *p2)
     }
   if (a2->expr->expr_type != EXPR_VARIABLE)
     return 1;
+  if (a1->expr->symtree->n.sym > a2->expr->symtree->n.sym)
+    return -1;
   return a1->expr->symtree->n.sym < a2->expr->symtree->n.sym;
 }
 
-- 
1.8.3.1

Re: [PATCH 7/6] fortran: fix pair_cmp qsort comparator

[Thomas Koenig]

Am 21.07.2017 um 16:29 schrieb Alexander Monakov:

> Bootstrapped and regtested on x86-64, OK for trunk?
> 
> 	* interface.c (pair_cmp): Fix gfc_symbol comparison.  Adjust comment.

OK.

Thanks for the patch!

Regards

	Thomas