[PATCH 0/5] Fix qsort comparison functions

[PATCH 0/5] Fix qsort comparison functions

[Yury Gribov]

Hi all,

This patchset fixes bugs in comparison functions used in qsort(3). 
Standard requires comparison functions to satisfy certain 
symmetry/transitivity axioms ("total ordering" in 
http://pubs.opengroup.org/onlinepubs/009695399/functions/qsort.html). 
Violation triggers undefined behavior which can e.g. cause qsort to 
produce invalid results (or even crash - check 
https://bugzilla.samba.org/show_bug.cgi?id=3959).

Most of the patches are pretty obvious except for no. 3 for which I was 
failed to devise a behavior-preserving fix.  I've Cc-ed the original 
authors in hope they'll be able to help.

I've verified all patches on x86_64-pc-linux-gnu (bootstrap + regression 
test).

NB: Bugs were found with SortChecker tool 
(https://github.com/yugr/sortcheck).

/Yury

[PATCH 1/5] Fix asymmetric comparison functions

[Yury Gribov]

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

Some obvious symmetry fixes.

Cc-ing
* Andrey (Belevantsev) for bb_top_order_comparator
* Andrew (MacLeod) for compare_case_labels
* Andrew (Pinski) for resort_field_decl_cmp
* Diego for pair_cmp
* Geoff for resort_method_name_cmp
* Jakub for compare_case_labels
* Jason for method_name_cmp
* Richard for insert_phi_nodes_compare_var_infos, compare_case_labels
* Steven for cmp_v_in_regset_pool

/Yury

[-- Attachment #2: 0001-Fix-asymmetric-comparison-functions.patch --]
[-- Type: text/x-patch, Size: 5375 bytes --]

From bf924dca4ccc3f8640438400e923a4c508e898e0 Mon Sep 17 00:00:00 2001
From: Yury Gribov <tetra2005@gmail.com>
Date: Sat, 12 Dec 2015 09:51:54 +0300
Subject: [PATCH 1/5] Fix asymmetric comparison functions.

Qsort requires user-defined comparison function to be
a total order. One of the requirements for this is being
symmetric i.e. return inverse results on element swap.
This patch fixes comparison functions to satisfy these
conditions.

2015-12-17  Yury Gribov  <tetra2005@gmail.com>

	* c-family/c-common.c (resort_field_decl_cmp):
	Make symmteric.
	* cp/class.c (method_name_cmp): Ditto.
	(resort_method_name_cmp): Ditto.
	* fortran/interface.c (pair_cmp): Ditto.
	* gimple.c (compare_case_labels): Ditto.
	* tree-into-ssa.c (insert_phi_nodes_compare_var_infos):
	Ditto.
	* tree-vrp.c (compare_case_labels): Ditto.
	* sel-sched-ir.c (cmp_v_in_regset_pool): Ditto.
	(bb_top_order_comparator): Ditto.
---
 gcc/c-family/c-common.c |  4 +++-
 gcc/cp/class.c          | 10 ++++++----
 gcc/fortran/interface.c |  6 +++++-
 gcc/gimple.c            |  4 +++-
 gcc/sel-sched-ir.c      |  5 +++--
 gcc/tree-into-ssa.c     |  5 +----
 gcc/tree-vrp.c          |  4 +++-
 7 files changed, 24 insertions(+), 14 deletions(-)

diff --git a/gcc/c-family/c-common.c b/gcc/c-family/c-common.c
index 9bc02fc..eecdfb5 100644
--- a/gcc/c-family/c-common.c
+++ b/gcc/c-family/c-common.c
@@ -9956,8 +9956,10 @@ resort_field_decl_cmp (const void *x_p, const void *y_p)
     resort_data.new_value (&d2, resort_data.cookie);
     if (d1 < d2)
       return -1;
+    if (d1 > d2)
+      return 1;
   }
-  return 1;
+  return 0;
 }
 
 /* Resort DECL_SORTED_FIELDS because pointers have been reordered.  */
diff --git a/gcc/cp/class.c b/gcc/cp/class.c
index 216a301..3a740d2 100644
--- a/gcc/cp/class.c
+++ b/gcc/cp/class.c
@@ -2188,9 +2188,9 @@ method_name_cmp (const void* m1_p, const void* m2_p)
     return -1;
   if (*m2 == NULL_TREE)
     return 1;
-  if (DECL_NAME (OVL_CURRENT (*m1)) < DECL_NAME (OVL_CURRENT (*m2)))
-    return -1;
-  return 1;
+  tree d1 = DECL_NAME (OVL_CURRENT (*m1));
+  tree d2 = DECL_NAME (OVL_CURRENT (*m2));
+  return d1 < d2 ? -1 : d1 > d2 ? 1 : 0;
 }
 
 /* This routine compares two fields like method_name_cmp but using the
@@ -2214,8 +2214,10 @@ resort_method_name_cmp (const void* m1_p, const void* m2_p)
     resort_data.new_value (&d2, resort_data.cookie);
     if (d1 < d2)
       return -1;
+    if (d1 > d2)
+      return 1;
   }
-  return 1;
+  return 0;
 }
 
 /* Resort TYPE_METHOD_VEC because pointers have been reordered.  */
diff --git a/gcc/fortran/interface.c b/gcc/fortran/interface.c
index bfd5d36..e4b93c8 100644
--- a/gcc/fortran/interface.c
+++ b/gcc/fortran/interface.c
@@ -3109,7 +3109,11 @@ pair_cmp (const void *p1, const void *p2)
     }
   if (a2->expr->expr_type != EXPR_VARIABLE)
     return 1;
-  return a1->expr->symtree->n.sym < a2->expr->symtree->n.sym;
+  if (a1->expr->symtree->n.sym < a2->expr->symtree->n.sym)
+    return 1;
+  if (a1->expr->symtree->n.sym > a2->expr->symtree->n.sym)
+    return -1;
+  return 0;
 }
 
 
diff --git a/gcc/gimple.c b/gcc/gimple.c
index bf552a7..51f515e 100644
--- a/gcc/gimple.c
+++ b/gcc/gimple.c
@@ -2774,7 +2774,9 @@ compare_case_labels (const void *p1, const void *p2)
   const_tree const case2 = *(const_tree const*)p2;
 
   /* The 'default' case label always goes first.  */
-  if (!CASE_LOW (case1))
+  if (!CASE_LOW (case1) && !CASE_LOW (case2))
+    return 0;
+  else if (!CASE_LOW (case1))
     return -1;
   else if (!CASE_LOW (case2))
     return 1;
diff --git a/gcc/sel-sched-ir.c b/gcc/sel-sched-ir.c
index 2a9aa10..2f53d22 100644
--- a/gcc/sel-sched-ir.c
+++ b/gcc/sel-sched-ir.c
@@ -959,7 +959,7 @@ cmp_v_in_regset_pool (const void *x, const void *xx)
     return 1;
   else if (r1 < r2)
     return -1;
-  gcc_unreachable ();
+  return 0;
 }
 
 /* Free the regset pool possibly checking for memory leaks.  */
@@ -5935,8 +5935,9 @@ bb_top_order_comparator (const void *x, const void *y)
      bbs with greater number should go earlier.  */
   if (rev_top_order_index[bb1->index] > rev_top_order_index[bb2->index])
     return -1;
-  else
+  else if (rev_top_order_index[bb1->index] < rev_top_order_index[bb2->index])
     return 1;
+  return 0;
 }
 
 /* Create a region for LOOP and return its number.  If we don't want
diff --git a/gcc/tree-into-ssa.c b/gcc/tree-into-ssa.c
index 5486d5c..f3b8c02 100644
--- a/gcc/tree-into-ssa.c
+++ b/gcc/tree-into-ssa.c
@@ -1041,10 +1041,7 @@ insert_phi_nodes_compare_var_infos (const void *a, const void *b)
 {
   const var_info *defa = *(var_info * const *)a;
   const var_info *defb = *(var_info * const *)b;
-  if (DECL_UID (defa->var) < DECL_UID (defb->var))
-    return -1;
-  else
-    return 1;
+  return DECL_UID (defa->var) - DECL_UID (defb->var);
 }
 
 /* Insert PHI nodes at the dominance frontier of blocks with variable
diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
index acbb70b..cd4eec8 100644
--- a/gcc/tree-vrp.c
+++ b/gcc/tree-vrp.c
@@ -5882,7 +5882,9 @@ compare_case_labels (const void *p1, const void *p2)
   else if (idx1 == idx2)
     {
       /* Make sure the default label is first in a group.  */
-      if (!CASE_LOW (ci1->expr))
+      if (!CASE_LOW (ci1->expr) && !CASE_LOW (ci2->expr))
+	return 0;
+      else if (!CASE_LOW (ci1->expr))
 	return -1;
       else if (!CASE_LOW (ci2->expr))
 	return 1;
-- 
1.9.1

Re: [PATCH 1/5] Fix asymmetric comparison functions

[Jakub Jelinek]

On Thu, Dec 17, 2015 at 11:58:30AM +0300, Yury Gribov wrote:
> 2015-12-17  Yury Gribov  <tetra2005@gmail.com>
> 
> 	* c-family/c-common.c (resort_field_decl_cmp):
> 	Make symmteric.
> 	* cp/class.c (method_name_cmp): Ditto.
> 	(resort_method_name_cmp): Ditto.
> 	* fortran/interface.c (pair_cmp): Ditto.

Note, c-family, cp and fortran have their own ChangeLog files, so
the entries without those prefixes need to go into each one and can't
refer to other ChangeLog through Ditto/Likewise etc.
Typo in symmteric.

That said, is this actually really a problem?  I mean, is qsort
allowed to call the comparison function with the same arguments?
I think lots of the comparison functions just assume that
for int cmpfn (const void *x, const void *y) x != y.
And if qsort can't call the comparison function with the same argument,
then perhaps the caller has some knowledge your checker does not, say
that the entries that would compare equal by the comparison function
simply can't appear in the array (so the caller knows that the comparison
function should never return 0).

> --- a/gcc/tree-vrp.c
> +++ b/gcc/tree-vrp.c
> @@ -5882,7 +5882,9 @@ compare_case_labels (const void *p1, const void *p2)
>    else if (idx1 == idx2)
>      {
>        /* Make sure the default label is first in a group.  */
> -      if (!CASE_LOW (ci1->expr))
> +      if (!CASE_LOW (ci1->expr) && !CASE_LOW (ci2->expr))
> +	return 0;
> +      else if (!CASE_LOW (ci1->expr))
>  	return -1;
>        else if (!CASE_LOW (ci2->expr))
>  	return 1;
> -- 
> 1.9.1

Say here, we know there is at most one default label in a switch, never
more.  So, unless qsort is allowed to call compare_case_labels
with p1 == p2 (which really doesn't make sense), this case just won't
happen.

	Jakub

Re: [PATCH 1/5] Fix asymmetric comparison functions

[Yury Gribov]

On 12/17/2015 02:39 PM, Jakub Jelinek wrote:
> On Thu, Dec 17, 2015 at 11:58:30AM +0300, Yury Gribov wrote:
>> 2015-12-17  Yury Gribov  <tetra2005@gmail.com>
>>
>> 	* c-family/c-common.c (resort_field_decl_cmp):
>> 	Make symmteric.
>> 	* cp/class.c (method_name_cmp): Ditto.
>> 	(resort_method_name_cmp): Ditto.
>> 	* fortran/interface.c (pair_cmp): Ditto.
>
> Note, c-family, cp and fortran have their own ChangeLog files, so
> the entries without those prefixes need to go into each one and can't
> refer to other ChangeLog through Ditto/Likewise etc.
> Typo in symmteric.

Right, thanks.

> That said, is this actually really a problem?  I mean, is qsort
> allowed to call the comparison function with the same arguments?
> I think lots of the comparison functions just assume that
> for int cmpfn (const void *x, const void *y) x != y.
> And if qsort can't call the comparison function with the same argument,
> then perhaps the caller has some knowledge your checker does not, say
> that the entries that would compare equal by the comparison function
> simply can't appear in the array (so the caller knows that the comparison
> function should never return 0).

Self-comparisons are certainly less dangerous than transitive ones. I 
personally not aware about libc's which can compare element to itself.

However
* comparing an element to itself still a valid thing for qsort to do
* most other comparison functions in GCC support this

>> --- a/gcc/tree-vrp.c
>> +++ b/gcc/tree-vrp.c
>> @@ -5882,7 +5882,9 @@ compare_case_labels (const void *p1, const void *p2)
>>     else if (idx1 == idx2)
>>       {
>>         /* Make sure the default label is first in a group.  */
>> -      if (!CASE_LOW (ci1->expr))
>> +      if (!CASE_LOW (ci1->expr) && !CASE_LOW (ci2->expr))
>> +	return 0;
>> +      else if (!CASE_LOW (ci1->expr))
>>   	return -1;
>>         else if (!CASE_LOW (ci2->expr))
>>   	return 1;
>> --
>> 1.9.1
>
> Say here, we know there is at most one default label in a switch, never
> more.  So, unless qsort is allowed to call compare_case_labels
> with p1 == p2 (which really doesn't make sense), this case just won't
> happen.

Re: [PATCH 1/5] Fix asymmetric comparison functions

[Yury Gribov]

On 12/17/2015 03:04 PM, Yury Gribov wrote:
> On 12/17/2015 02:39 PM, Jakub Jelinek wrote:
>> On Thu, Dec 17, 2015 at 11:58:30AM +0300, Yury Gribov wrote:
>>> 2015-12-17  Yury Gribov  <tetra2005@gmail.com>
>>>
>>>     * c-family/c-common.c (resort_field_decl_cmp):
>>>     Make symmteric.
>>>     * cp/class.c (method_name_cmp): Ditto.
>>>     (resort_method_name_cmp): Ditto.
>>>     * fortran/interface.c (pair_cmp): Ditto.
>>
>> Note, c-family, cp and fortran have their own ChangeLog files, so
>> the entries without those prefixes need to go into each one and can't
>> refer to other ChangeLog through Ditto/Likewise etc.
>> Typo in symmteric.
>
> Right, thanks.
>
>> That said, is this actually really a problem?  I mean, is qsort
>> allowed to call the comparison function with the same arguments?
>> I think lots of the comparison functions just assume that
>> for int cmpfn (const void *x, const void *y) x != y.
>> And if qsort can't call the comparison function with the same argument,
>> then perhaps the caller has some knowledge your checker does not, say
>> that the entries that would compare equal by the comparison function
>> simply can't appear in the array (so the caller knows that the comparison
>> function should never return 0).
>
> Self-comparisons are certainly less dangerous than transitive ones. I
> personally not aware about libc's which can compare element to itself.

Jakub,

So it seems most people generally agree that self-comparisons (cmp(x,x) 
== 0) are useless and don't need to be checked or fixed. What about 
ensuring symmetry i.e. that cmp(x, y) == -cmp(y, x) forall x, y?  One of 
the bugs (pair_cmp in fortran/interface.c) is exactly about this.

> However
> * comparing an element to itself still a valid thing for qsort to do
> * most other comparison functions in GCC support this
>
>>> --- a/gcc/tree-vrp.c
>>> +++ b/gcc/tree-vrp.c
>>> @@ -5882,7 +5882,9 @@ compare_case_labels (const void *p1, const void
>>> *p2)
>>>     else if (idx1 == idx2)
>>>       {
>>>         /* Make sure the default label is first in a group.  */
>>> -      if (!CASE_LOW (ci1->expr))
>>> +      if (!CASE_LOW (ci1->expr) && !CASE_LOW (ci2->expr))
>>> +    return 0;
>>> +      else if (!CASE_LOW (ci1->expr))
>>>       return -1;
>>>         else if (!CASE_LOW (ci2->expr))
>>>       return 1;
>>> --
>>> 1.9.1
>>
>> Say here, we know there is at most one default label in a switch, never
>> more.  So, unless qsort is allowed to call compare_case_labels
>> with p1 == p2 (which really doesn't make sense), this case just won't
>> happen.
>
>
>

Re: [PATCH 1/5] Fix asymmetric comparison functions

[Jakub Jelinek]

On Fri, Dec 18, 2015 at 10:40:40PM +0300, Yury Gribov wrote:
> So it seems most people generally agree that self-comparisons (cmp(x,x) ==
> 0) are useless and don't need to be checked or fixed. What about ensuring
> symmetry i.e. that cmp(x, y) == -cmp(y, x) forall x, y?  One of the bugs
> (pair_cmp in fortran/interface.c) is exactly about this.

Ensuring symmetry for x != y is of course very much desirable.
So, if you could change your qsort interposer so that it for each comparison
x != y calls both cmp (x, y) and cmp (y, x) and asserts that
int r = cmp (x, y);
int ir = cmp (y, x);
if (r > 0) assert (ir < 0);
else if (r < 0) assert (ir > 0);
else assert (ir == 0);
it would be greatly appreciated.  Note, the standard only talks about < 0, 0
and > 0, so it is fine if cmp (x, y) returns 231 and cmp (y, x) returns -142.

	Jakub

Re: [PATCH 1/5] Fix asymmetric comparison functions

[Yury Gribov]

On 12/18/2015 11:07 PM, Jakub Jelinek wrote:
> On Fri, Dec 18, 2015 at 10:40:40PM +0300, Yury Gribov wrote:
>> So it seems most people generally agree that self-comparisons (cmp(x,x) ==
>> 0) are useless and don't need to be checked or fixed. What about ensuring
>> symmetry i.e. that cmp(x, y) == -cmp(y, x) forall x, y?  One of the bugs
>> (pair_cmp in fortran/interface.c) is exactly about this.
>
> Ensuring symmetry for x != y is of course very much desirable.
> So, if you could change your qsort interposer so that it for each comparison
> x != y calls both cmp (x, y) and cmp (y, x) and asserts that
> int r = cmp (x, y);
> int ir = cmp (y, x);
> if (r > 0) assert (ir < 0);
> else if (r < 0) assert (ir > 0);
> else assert (ir == 0);
> it would be greatly appreciated.  Note, the standard only talks about < 0, 0
> and > 0, so it is fine if cmp (x, y) returns 231 and cmp (y, x) returns -142.

Sure, I've already bumped into this with other projects.

I'll update my checker and get back with a reduced patchset then.

/Yura

Re: [PATCH 1/5] Fix asymmetric comparison functions

[Richard Biener]

On Thu, 17 Dec 2015, Yury Gribov wrote:

> Some obvious symmetry fixes.
> 
> Cc-ing
> * Andrey (Belevantsev) for bb_top_order_comparator
> * Andrew (MacLeod) for compare_case_labels
> * Andrew (Pinski) for resort_field_decl_cmp
> * Diego for pair_cmp
> * Geoff for resort_method_name_cmp
> * Jakub for compare_case_labels
> * Jason for method_name_cmp
> * Richard for insert_phi_nodes_compare_var_infos, compare_case_labels
> * Steven for cmp_v_in_regset_pool

So for compare_case_labels we only ever have one label with
!CASE_LOW - which means you only run into the case that needs
!CASE_LOW && !CASE_LOW if comparing an element with itself, correct?

In this case (missing "same element" handling rather than symmetry
fixing) I'd prefer a

 if (case1 == case2)
   return 0;

So just to confirm - do the patches also contain same element
compare fixings?

Richard.

Re: [PATCH 1/5] Fix asymmetric comparison functions

[Yury Gribov]

On 12/17/2015 02:41 PM, Richard Biener wrote:
> On Thu, 17 Dec 2015, Yury Gribov wrote:
>
>> Some obvious symmetry fixes.
>>
>> Cc-ing
>> * Andrey (Belevantsev) for bb_top_order_comparator
>> * Andrew (MacLeod) for compare_case_labels
>> * Andrew (Pinski) for resort_field_decl_cmp
>> * Diego for pair_cmp
>> * Geoff for resort_method_name_cmp
>> * Jakub for compare_case_labels
>> * Jason for method_name_cmp
>> * Richard for insert_phi_nodes_compare_var_infos, compare_case_labels
>> * Steven for cmp_v_in_regset_pool
>
> So for compare_case_labels we only ever have one label with
> !CASE_LOW - which means you only run into the case that needs
> !CASE_LOW && !CASE_LOW if comparing an element with itself, correct?
>
> In this case (missing "same element" handling rather than symmetry
> fixing) I'd prefer a
>
>   if (case1 == case2)
>     return 0;
>
> So just to confirm - do the patches also contain same element
> compare fixings?

Yes, that's a fix for same element.  How about adding if + gcc_assert 
that both cases can't be NULL otherwise?

/Yury

Re: [PATCH 1/5] Fix asymmetric comparison functions

[Jakub Jelinek]

On Thu, Dec 17, 2015 at 02:47:29PM +0300, Yury Gribov wrote:
> On 12/17/2015 02:41 PM, Richard Biener wrote:
> >On Thu, 17 Dec 2015, Yury Gribov wrote:
> >
> >>Some obvious symmetry fixes.
> >>
> >>Cc-ing
> >>* Andrey (Belevantsev) for bb_top_order_comparator
> >>* Andrew (MacLeod) for compare_case_labels
> >>* Andrew (Pinski) for resort_field_decl_cmp
> >>* Diego for pair_cmp
> >>* Geoff for resort_method_name_cmp
> >>* Jakub for compare_case_labels
> >>* Jason for method_name_cmp
> >>* Richard for insert_phi_nodes_compare_var_infos, compare_case_labels
> >>* Steven for cmp_v_in_regset_pool
> >
> >So for compare_case_labels we only ever have one label with
> >!CASE_LOW - which means you only run into the case that needs
> >!CASE_LOW && !CASE_LOW if comparing an element with itself, correct?
> >
> >In this case (missing "same element" handling rather than symmetry
> >fixing) I'd prefer a
> >
> >  if (case1 == case2)
> >    return 0;
> >
> >So just to confirm - do the patches also contain same element
> >compare fixings?
> 
> Yes, that's a fix for same element.  How about adding if + gcc_assert that
> both cases can't be NULL otherwise?

Some of the qsort comparison functions are hot paths, we don't really want
to slow them down.  So, if anything, gcc_checking_assert rather than
gcc_assert.
But, which qsort is so lame that it calls comparison on the same element?

	Jakub

Re: [PATCH 1/5] Fix asymmetric comparison functions

[Richard Biener]

On Thu, 17 Dec 2015, Yury Gribov wrote:

> On 12/17/2015 02:41 PM, Richard Biener wrote:
> > On Thu, 17 Dec 2015, Yury Gribov wrote:
> > 
> > > Some obvious symmetry fixes.
> > > 
> > > Cc-ing
> > > * Andrey (Belevantsev) for bb_top_order_comparator
> > > * Andrew (MacLeod) for compare_case_labels
> > > * Andrew (Pinski) for resort_field_decl_cmp
> > > * Diego for pair_cmp
> > > * Geoff for resort_method_name_cmp
> > > * Jakub for compare_case_labels
> > > * Jason for method_name_cmp
> > > * Richard for insert_phi_nodes_compare_var_infos, compare_case_labels
> > > * Steven for cmp_v_in_regset_pool
> > 
> > So for compare_case_labels we only ever have one label with
> > !CASE_LOW - which means you only run into the case that needs
> > !CASE_LOW && !CASE_LOW if comparing an element with itself, correct?
> > 
> > In this case (missing "same element" handling rather than symmetry
> > fixing) I'd prefer a
> > 
> >   if (case1 == case2)
> >     return 0;
> > 
> > So just to confirm - do the patches also contain same element
> > compare fixings?
> 
> Yes, that's a fix for same element.  How about adding if + gcc_assert that
> both cases can't be NULL otherwise?

Well, does qsort require the compare function to result in zero
for same elements when the sequence to be sorted doesn't contain
duplicates?

If an assert works for you that hints at these places found via static
analysis rather than a runtime fuzzer?

Richard.

Re: [PATCH 1/5] Fix asymmetric comparison functions

[Yury Gribov]

On 12/17/2015 02:59 PM, Richard Biener wrote:
> On Thu, 17 Dec 2015, Yury Gribov wrote:
>
>> On 12/17/2015 02:41 PM, Richard Biener wrote:
>>> On Thu, 17 Dec 2015, Yury Gribov wrote:
>>>
>>>> Some obvious symmetry fixes.
>>>>
>>>> Cc-ing
>>>> * Andrey (Belevantsev) for bb_top_order_comparator
>>>> * Andrew (MacLeod) for compare_case_labels
>>>> * Andrew (Pinski) for resort_field_decl_cmp
>>>> * Diego for pair_cmp
>>>> * Geoff for resort_method_name_cmp
>>>> * Jakub for compare_case_labels
>>>> * Jason for method_name_cmp
>>>> * Richard for insert_phi_nodes_compare_var_infos, compare_case_labels
>>>> * Steven for cmp_v_in_regset_pool
>>>
>>> So for compare_case_labels we only ever have one label with
>>> !CASE_LOW - which means you only run into the case that needs
>>> !CASE_LOW && !CASE_LOW if comparing an element with itself, correct?
>>>
>>> In this case (missing "same element" handling rather than symmetry
>>> fixing) I'd prefer a
>>>
>>>    if (case1 == case2)
>>>      return 0;
>>>
>>> So just to confirm - do the patches also contain same element
>>> compare fixings?
>>
>> Yes, that's a fix for same element.  How about adding if + gcc_assert that
>> both cases can't be NULL otherwise?
>
> Well, does qsort require the compare function to result in zero
> for same elements when the sequence to be sorted doesn't contain
> duplicates?

Sure, that's part of total ordering requirement in standard.

> If an assert works for you that hints at these places found via static
> analysis rather than a runtime fuzzer?

Sorry, not sure I fully understood but - yes, adding assertion would 
typically allow for better checking by static analyzers.

/Yura

Re: [PATCH 1/5] Fix asymmetric comparison functions

[Richard Biener]

On Thu, 17 Dec 2015, Yury Gribov wrote:

> On 12/17/2015 02:59 PM, Richard Biener wrote:
> > On Thu, 17 Dec 2015, Yury Gribov wrote:
> > 
> > > On 12/17/2015 02:41 PM, Richard Biener wrote:
> > > > On Thu, 17 Dec 2015, Yury Gribov wrote:
> > > > 
> > > > > Some obvious symmetry fixes.
> > > > > 
> > > > > Cc-ing
> > > > > * Andrey (Belevantsev) for bb_top_order_comparator
> > > > > * Andrew (MacLeod) for compare_case_labels
> > > > > * Andrew (Pinski) for resort_field_decl_cmp
> > > > > * Diego for pair_cmp
> > > > > * Geoff for resort_method_name_cmp
> > > > > * Jakub for compare_case_labels
> > > > > * Jason for method_name_cmp
> > > > > * Richard for insert_phi_nodes_compare_var_infos, compare_case_labels
> > > > > * Steven for cmp_v_in_regset_pool
> > > > 
> > > > So for compare_case_labels we only ever have one label with
> > > > !CASE_LOW - which means you only run into the case that needs
> > > > !CASE_LOW && !CASE_LOW if comparing an element with itself, correct?
> > > > 
> > > > In this case (missing "same element" handling rather than symmetry
> > > > fixing) I'd prefer a
> > > > 
> > > >    if (case1 == case2)
> > > >      return 0;
> > > > 
> > > > So just to confirm - do the patches also contain same element
> > > > compare fixings?
> > > 
> > > Yes, that's a fix for same element.  How about adding if + gcc_assert that
> > > both cases can't be NULL otherwise?
> > 
> > Well, does qsort require the compare function to result in zero
> > for same elements when the sequence to be sorted doesn't contain
> > duplicates?
> 
> Sure, that's part of total ordering requirement in standard.
> 
> > If an assert works for you that hints at these places found via static
> > analysis rather than a runtime fuzzer?
> 
> Sorry, not sure I fully understood but - yes, adding assertion would typically
> allow for better checking by static analyzers.

The question was if you actually observed the case to happen with a
testcase (and whatever mungled qsort implementation) or whether
it was a theoretical outcome computed by a static analyzer.

That is, whether you could hand me a testcase where it happens
or not.

Richard.

Re: [PATCH 1/5] Fix asymmetric comparison functions

[Yury Gribov]

On 12/17/2015 03:25 PM, Richard Biener wrote:
> On Thu, 17 Dec 2015, Yury Gribov wrote:
>
>> On 12/17/2015 02:59 PM, Richard Biener wrote:
>>> On Thu, 17 Dec 2015, Yury Gribov wrote:
>>>
>>>> On 12/17/2015 02:41 PM, Richard Biener wrote:
>>>>> On Thu, 17 Dec 2015, Yury Gribov wrote:
>>>>>
>>>>>> Some obvious symmetry fixes.
>>>>>>
>>>>>> Cc-ing
>>>>>> * Andrey (Belevantsev) for bb_top_order_comparator
>>>>>> * Andrew (MacLeod) for compare_case_labels
>>>>>> * Andrew (Pinski) for resort_field_decl_cmp
>>>>>> * Diego for pair_cmp
>>>>>> * Geoff for resort_method_name_cmp
>>>>>> * Jakub for compare_case_labels
>>>>>> * Jason for method_name_cmp
>>>>>> * Richard for insert_phi_nodes_compare_var_infos, compare_case_labels
>>>>>> * Steven for cmp_v_in_regset_pool
>>>>>
>>>>> So for compare_case_labels we only ever have one label with
>>>>> !CASE_LOW - which means you only run into the case that needs
>>>>> !CASE_LOW && !CASE_LOW if comparing an element with itself, correct?
>>>>>
>>>>> In this case (missing "same element" handling rather than symmetry
>>>>> fixing) I'd prefer a
>>>>>
>>>>>     if (case1 == case2)
>>>>>       return 0;
>>>>>
>>>>> So just to confirm - do the patches also contain same element
>>>>> compare fixings?
>>>>
>>>> Yes, that's a fix for same element.  How about adding if + gcc_assert that
>>>> both cases can't be NULL otherwise?
>>>
>>> Well, does qsort require the compare function to result in zero
>>> for same elements when the sequence to be sorted doesn't contain
>>> duplicates?
>>
>> Sure, that's part of total ordering requirement in standard.
>>
>>> If an assert works for you that hints at these places found via static
>>> analysis rather than a runtime fuzzer?
>>
>> Sorry, not sure I fully understood but - yes, adding assertion would typically
>> allow for better checking by static analyzers.
>
> The question was if you actually observed the case to happen with a
> testcase (and whatever mungled qsort implementation) or whether
> it was a theoretical outcome computed by a static analyzer.
>
> That is, whether you could hand me a testcase where it happens
> or not.

Well, this was detected by calling qsort(x, x) and checking that return 
value is zero in qsort interceptor. So I guess it's more of 
"theoretical" sort.

/Yura

Re: [PATCH 1/5] Fix asymmetric comparison functions

[Andrey Belevantsev]

Hello,

On 17.12.2015 11:58, Yury Gribov wrote:
> Some obvious symmetry fixes.
>
> Cc-ing
> * Andrey (Belevantsev) for bb_top_order_comparator

Here, as Jakub mentioned, we assume that the argument addresses will never 
be equal, thus that would always be different basic blocks (the comparator 
is used for providing a custom sort over loop body bbs) and you don't need 
a return 0 there.  You can put there gcc_unreachable instead as in ...

> * Andrew (MacLeod) for compare_case_labels
> * Andrew (Pinski) for resort_field_decl_cmp
> * Diego for pair_cmp
> * Geoff for resort_method_name_cmp
> * Jakub for compare_case_labels
> * Jason for method_name_cmp
> * Richard for insert_phi_nodes_compare_var_infos, compare_case_labels
> * Steven for cmp_v_in_regset_pool

... this case -- here gcc_unreachable () marks that we're sorting pool 
pointers and their values are always different.  Please do not remove it.

Yours,
Andrey

>
> /Yury

Re: [PATCH 1/5] Fix asymmetric comparison functions

[Yury Gribov]

On 12/17/2015 02:58 PM, Andrey Belevantsev wrote:
> Hello,
>
> On 17.12.2015 11:58, Yury Gribov wrote:
>> Some obvious symmetry fixes.
>>
>> Cc-ing
>> * Andrey (Belevantsev) for bb_top_order_comparator
>
> Here, as Jakub mentioned, we assume that the argument addresses will
> never be equal,

The problem is that this is not guaranteed.

> thus that would always be different basic blocks (the
> comparator is used for providing a custom sort over loop body bbs) and
> you don't need a return 0 there.  You can put there gcc_unreachable
> instead as in ...
>
>> * Andrew (MacLeod) for compare_case_labels
>> * Andrew (Pinski) for resort_field_decl_cmp
>> * Diego for pair_cmp
>> * Geoff for resort_method_name_cmp
>> * Jakub for compare_case_labels
>> * Jason for method_name_cmp
>> * Richard for insert_phi_nodes_compare_var_infos, compare_case_labels
>> * Steven for cmp_v_in_regset_pool
>
> ... this case -- here gcc_unreachable () marks that we're sorting pool
> pointers and their values are always different.  Please do not remove it.

Same here.

/Yury

Re: [PATCH 1/5] Fix asymmetric comparison functions

[Andrey Belevantsev]

On 17.12.2015 15:13, Yury Gribov wrote:
> On 12/17/2015 02:58 PM, Andrey Belevantsev wrote:
>> Hello,
>>
>> On 17.12.2015 11:58, Yury Gribov wrote:
>>> Some obvious symmetry fixes.
>>>
>>> Cc-ing
>>> * Andrey (Belevantsev) for bb_top_order_comparator
>>
>> Here, as Jakub mentioned, we assume that the argument addresses will
>> never be equal,
>
> The problem is that this is not guaranteed.

Well, if the consensus is that this is indeed the case, you're free to 
change both places as you suggest.

Yours,
Andrey

>
>> thus that would always be different basic blocks (the
>> comparator is used for providing a custom sort over loop body bbs) and
>> you don't need a return 0 there.  You can put there gcc_unreachable
>> instead as in ...
>>
>>> * Andrew (MacLeod) for compare_case_labels
>>> * Andrew (Pinski) for resort_field_decl_cmp
>>> * Diego for pair_cmp
>>> * Geoff for resort_method_name_cmp
>>> * Jakub for compare_case_labels
>>> * Jason for method_name_cmp
>>> * Richard for insert_phi_nodes_compare_var_infos, compare_case_labels
>>> * Steven for cmp_v_in_regset_pool
>>
>> ... this case -- here gcc_unreachable () marks that we're sorting pool
>> pointers and their values are always different.  Please do not remove it.
>
> Same here.
>
> /Yury

Re: [PATCH 1/5] Fix asymmetric comparison functions

[Andrew Pinski]

On Thu, Dec 17, 2015 at 12:58 AM, Yury Gribov <y.gribov@samsung.com> wrote:
> Some obvious symmetry fixes.
>
> Cc-ing
> * Andrey (Belevantsev) for bb_top_order_comparator
> * Andrew (MacLeod) for compare_case_labels
> * Andrew (Pinski) for resort_field_decl_cmp

IIRC this was actually not written by me but I copied it back from an
older version.  But then again this was over 10 years ago so I don't
remember the history on this any more.

Thanks,
Andrew

> * Diego for pair_cmp
> * Geoff for resort_method_name_cmp
> * Jakub for compare_case_labels
> * Jason for method_name_cmp
> * Richard for insert_phi_nodes_compare_var_infos, compare_case_labels
> * Steven for cmp_v_in_regset_pool
>
> /Yury

Re: [PATCH 1/5] Fix asymmetric comparison functions

[Jason Merrill]

The C++ changes are also for handling comparing an element to itself, 
which shouldn't happen; I'd prefer a gcc_checking_assert that it doesn't.

Jason

[PATCH 2/5] Fix more asymmetric comparison functions

[Yury Gribov]

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

Some more symmetry fixes.  These were detected manually (not via 
automatic analysis by SortChecker)
so I've put them to a separate patch.

Cc-ing
* Alexandre for sel_rank_for_schedule
* Ben for cmp_modes
* Jakub for range_entry_cmp
* Richard for sort_bbs_in_loop_postorder_cmp, 
sort_locs_in_loop_postorder_cmp, find_ref_loc_in_loop_cmp and 
dr_group_sort_cmp

/Yury

[-- Attachment #2: 0002-Fix-more-asymmetric-comparison-functions.patch --]
[-- Type: text/x-patch, Size: 4831 bytes --]

From 5716669d0b88265ee610ad139a0dc4152d1c20f3 Mon Sep 17 00:00:00 2001
From: Yury Gribov <tetra2005@gmail.com>
Date: Sat, 12 Dec 2015 10:27:45 +0300
Subject: [PATCH 2/5] Fix more asymmetric comparison functions.

2015-12-17  Yury Gribov  <tetra2005@gmail.com>

	* genmodes.c (cmp_modes): Make symmetric.
	* sel-sched.c (sel_rank_for_schedule): Ditto.
	* tree-ssa-loop-im.c (sort_bbs_in_loop_postorder_cmp):
	(sort_locs_in_loop_postorder_cmp):
	(find_ref_loc_in_loop_cmp): Check invariant.
	* tree-ssa-reassoc.c (range_entry_cmp): Make symmetric.
	* tree-vect-data-refs (dr_group_sort_cmp): Ditto.
---
 gcc/genmodes.c            |  6 ++++--
 gcc/sel-sched.c           |  4 +++-
 gcc/tree-ssa-loop-im.c    | 19 +++++++++++++++----
 gcc/tree-ssa-reassoc.c    |  8 +++-----
 gcc/tree-vect-data-refs.c |  7 ++++---
 5 files changed, 29 insertions(+), 15 deletions(-)

diff --git a/gcc/genmodes.c b/gcc/genmodes.c
index 15d62a0..f78a4da 100644
--- a/gcc/genmodes.c
+++ b/gcc/genmodes.c
@@ -813,8 +813,9 @@ cmp_modes (const void *a, const void *b)
     {
       if (m->counter < n->counter)
 	return -1;
-      else
+      else if (m->counter > n->counter)
 	return 1;
+      return 0;
     }
 
   if (m->component->bytesize > n->component->bytesize)
@@ -829,8 +830,9 @@ cmp_modes (const void *a, const void *b)
 
   if (m->counter < n->counter)
     return -1;
-  else
+  else if (m->counter > n->counter)
     return 1;
+  return 0;
 }
 
 static void
diff --git a/gcc/sel-sched.c b/gcc/sel-sched.c
index aebc2d9..c6efe9b 100644
--- a/gcc/sel-sched.c
+++ b/gcc/sel-sched.c
@@ -3343,7 +3343,9 @@ sel_rank_for_schedule (const void *x, const void *y)
   tmp2_insn = EXPR_INSN_RTX (tmp2);
 
   /* Schedule debug insns as early as possible.  */
-  if (DEBUG_INSN_P (tmp_insn) && !DEBUG_INSN_P (tmp2_insn))
+  if (DEBUG_INSN_P (tmp_insn) && DEBUG_INSN_P (tmp2_insn))
+    return 0;
+  else if (DEBUG_INSN_P (tmp_insn))
     return -1;
   else if (DEBUG_INSN_P (tmp2_insn))
     return 1;
diff --git a/gcc/tree-ssa-loop-im.c b/gcc/tree-ssa-loop-im.c
index 9b1b815..b53a490 100644
--- a/gcc/tree-ssa-loop-im.c
+++ b/gcc/tree-ssa-loop-im.c
@@ -1504,7 +1504,11 @@ sort_bbs_in_loop_postorder_cmp (const void *bb1_, const void *bb2_)
   struct loop *loop2 = bb2->loop_father;
   if (loop1->num == loop2->num)
     return 0;
-  return bb_loop_postorder[loop1->num] < bb_loop_postorder[loop2->num] ? -1 : 1;
+  gcc_assert(bb_loop_postorder[loop1->num] != bb_loop_postorder[loop2->num]);
+  if (bb_loop_postorder[loop1->num] < bb_loop_postorder[loop2->num])
+    return -1;
+  else
+    return 1;
 }
 
 /* qsort sort function to sort ref locs after their loop fathers postorder.  */
@@ -1518,7 +1522,11 @@ sort_locs_in_loop_postorder_cmp (const void *loc1_, const void *loc2_)
   struct loop *loop2 = gimple_bb (loc2->stmt)->loop_father;
   if (loop1->num == loop2->num)
     return 0;
-  return bb_loop_postorder[loop1->num] < bb_loop_postorder[loop2->num] ? -1 : 1;
+  gcc_assert(bb_loop_postorder[loop1->num] != bb_loop_postorder[loop2->num]);
+  if (bb_loop_postorder[loop1->num] < bb_loop_postorder[loop2->num])
+    return -1;
+  else
+    return 1;
 }
 
 /* Gathers memory references in loops.  */
@@ -1625,8 +1633,11 @@ find_ref_loc_in_loop_cmp (const void *loop_, const void *loc_)
   if (loop->num  == loc_loop->num
       || flow_loop_nested_p (loop, loc_loop))
     return 0;
-  return (bb_loop_postorder[loop->num] < bb_loop_postorder[loc_loop->num]
-	  ? -1 : 1);
+  gcc_assert(bb_loop_postorder[loop->num] != bb_loop_postorder[loc_loop->num]);
+  if (bb_loop_postorder[loop->num] < bb_loop_postorder[loc_loop->num])
+    return -1;
+  else
+    return 1;
 }
 
 /* Iterates over all locations of REF in LOOP and its subloops calling
diff --git a/gcc/tree-ssa-reassoc.c b/gcc/tree-ssa-reassoc.c
index e54700e..472c8b1 100644
--- a/gcc/tree-ssa-reassoc.c
+++ b/gcc/tree-ssa-reassoc.c
@@ -2018,11 +2018,9 @@ range_entry_cmp (const void *a, const void *b)
 
   if (p->idx < q->idx)
     return -1;
-  else
-    {
-      gcc_checking_assert (p->idx > q->idx);
-      return 1;
-    }
+  else if (p->idx > q->idx)
+    return 1;
+  return 0;
 }
 
 /* Helper routine of optimize_range_test.
diff --git a/gcc/tree-vect-data-refs.c b/gcc/tree-vect-data-refs.c
index 4c566c8..7755aaa 100644
--- a/gcc/tree-vect-data-refs.c
+++ b/gcc/tree-vect-data-refs.c
@@ -2643,9 +2643,10 @@ dr_group_sort_cmp (const void *dra_, const void *drb_)
 
   /* Then sort after DR_INIT.  In case of identical DRs sort after stmt UID.  */
   cmp = tree_int_cst_compare (DR_INIT (dra), DR_INIT (drb));
-  if (cmp == 0)
-    return gimple_uid (DR_STMT (dra)) < gimple_uid (DR_STMT (drb)) ? -1 : 1;
-  return cmp;
+  if (cmp)
+    return cmp;
+
+  return gimple_uid (DR_STMT (dra)) - gimple_uid (DR_STMT (drb));
 }
 
 /* Function vect_analyze_data_ref_accesses.
-- 
1.9.1

[PATCH 3/5] "Fix" intransitive comparison in reload_pseudo_compare_func

[Yury Gribov]

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

This patch fixes intransitive comparison in reload_pseudo_compare_func. 
Imagine the following
situation:
1) bitmap_bit_p is unset for A and B but set for C
2) A < B (due to early ira_reg_class_max_nregs comparison)
3) B < C (due to following regno_assign_info comparison)

It may then easily happen that A > C (due to regno_assign_info 
comparison) which violates the transitiveness requirement of total ordering.

Unfortunately I'm not sure how to properly fix this so Cc-ing Vladimir 
for help.

/Yury

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: 0003-Fix-intransitive-comparison-in-reload_pseudo_compare.patch --]
[-- Type: text/x-patch; name="0003-Fix-intransitive-comparison-in-reload_pseudo_compare.patch", Size: 3154 bytes --]

From 83da5d11c4f013dd14c1ea0c1722c108d80f58ed Mon Sep 17 00:00:00 2001
From: Yury Gribov <tetra2005@gmail.com>
Date: Sat, 12 Dec 2015 10:08:45 +0300
Subject: [PATCH 3/5] "Fix" intransitive comparison in
 reload_pseudo_compare_func.

2015-12-17  Yury Gribov  <tetra2005@gmail.com>

	* lra-assigns.c (reload_pseudo_compare_func):
	Make transitive.

Error message:
Dec 10 00:33:18 yugr-ubuntu1404 : cc1plus[612]: qsort: comparison function is not transitive (comparison function 0x87bc50 (/home/yugr/build/gcc-4.9.3-patched-bootstrap/gcc/cc1plus+47bc50), called from 0x87d25c (/home/yugr/build/gcc-4.9.3-patched-bootstrap/gcc/cc1plus+47d25c), cmdline is "/home/yugr/build/gcc-4.9.3-patched-bootstrap/./gcc/cc1plus -quiet -nostdinc++ -I . -I /home/yugr/src/gcc-4.9.3-patched/libsanitizer/tsan -I .. -I /home/yugr/src/gcc-4.9.3-patched/libsanitizer -I /home/yugr/src/gcc-4.9.3-patched/libsanitizer/include -I ../../libstdc++-v3/include -I ../../libstdc++-v3/include/x86_64-unknown-linux-gnu -I /home/yugr/src/gcc-4.9.3-patched/libsanitizer/../libstdc++-v3/libsupc++ -imultiarch x86_64-linux-gnu -iprefix /home/yugr/build/gcc-4.9.3-patched-bootstrap/gcc/../lib/gcc/x86_64-unknown-linux-gnu/4.9.3/ -isystem /home/yugr/build/gcc-4.9.3-patched-bootstrap/./gcc/include -isystem /home/yugr/build/gcc-4.9.3-patched-bootstrap/./gcc/include-fixed -MD .libs/tsan_interface_atomic.d -MF .deps/tsan_interface_atomic.Tpo -MP -MT tsan_interface_atomic.lo -D_GNU_SOURCE -D _GNU_SOURCE -D _DEBUG -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -D _GNU_SOURCE -D PIC -isystem /home/yugr/install/gcc-4.9.3/x86_64-unknown-linux-gnu/include -isystem /home/yugr/install/gcc-4.9.3/x86_64-unknown-linux-gnu/sys-include /home/yugr/src/gcc-4.9.3-patched/libsanitizer/tsan/tsan_interface_atomic.cc -quiet -dumpbase tsan_interface_atomic.cc -mtune=generic -march=x86-64 -auxbase-strip .libs/tsan_interface_atomic.o -g -O2 -Wall -Wextra -Wno-unused-parameter -Wwrite-strings -Wpedantic -Wno-long-long -Wno-variadic-macros -fno-builtin -fno-exceptions -fno-rtti -fomit-frame-pointer -funwind-tables -fvisibility=hidden -fPIC -o /tmp/cc3IPd7A.s")
---
 gcc/lra-assigns.c | 7 +------
 1 file changed, 1 insertion(+), 6 deletions(-)

diff --git a/gcc/lra-assigns.c b/gcc/lra-assigns.c
index 2a9ff21..94f3e66 100644
--- a/gcc/lra-assigns.c
+++ b/gcc/lra-assigns.c
@@ -208,12 +208,7 @@ reload_pseudo_compare_func (const void *v1p, const void *v2p)
     return diff;
   if ((diff
        = (ira_reg_class_max_nregs[cl2][lra_reg_info[r2].biggest_mode]
-	  - ira_reg_class_max_nregs[cl1][lra_reg_info[r1].biggest_mode])) != 0
-      /* 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.  */
-      && ! bitmap_bit_p (&non_reload_pseudos, r1)
-      && ! bitmap_bit_p (&non_reload_pseudos, r2))
+	  - ira_reg_class_max_nregs[cl1][lra_reg_info[r1].biggest_mode])) != 0)
     return diff;
   if ((diff = (regno_assign_info[regno_assign_info[r2].first].freq
 	       - regno_assign_info[regno_assign_info[r1].first].freq)) != 0)
-- 
1.9.1

Re: [PATCH 3/5] "Fix" intransitive comparison in reload_pseudo_compare_func

[Vladimir Makarov]

On 12/17/2015 04:00 AM, Yury Gribov wrote:
> This patch fixes intransitive comparison in 
> reload_pseudo_compare_func. Imagine the following
> situation:
> 1) bitmap_bit_p is unset for A and B but set for C
> 2) A < B (due to early ira_reg_class_max_nregs comparison)
> 3) B < C (due to following regno_assign_info comparison)
>
> It may then easily happen that A > C (due to regno_assign_info 
> comparison) which violates the transitiveness requirement of total 
> ordering.
>
> Unfortunately I'm not sure how to properly fix this so Cc-ing Vladimir 
> for help.
>
   Yury, thanks for reporting this.  Yes that could be a problem but I 
can not approve this patch as it might result in *significant* 
performance degradation.  I remember the code.  What you propose is the 
original patch (PR57878) and it was exactly modified to the current 
version because of the negative performance impact.  The current code is 
safe although it might result into infinite cycling for some sort 
algorithms but not for used qsort.

   I'll think how to fix it better. Probably I will need two comparison 
functions for different assignment iterations.  The solution will need 
benchmarking as the code is critical for LRA performance.  Could you 
fill a bug report in order not to forget the issue.

Re: [PATCH 3/5] "Fix" intransitive comparison in reload_pseudo_compare_func

[Yury Gribov]

On 12/17/2015 10:36 PM, Vladimir Makarov wrote:
> On 12/17/2015 04:00 AM, Yury Gribov wrote:
>> This patch fixes intransitive comparison in
>> reload_pseudo_compare_func. Imagine the following
>> situation:
>> 1) bitmap_bit_p is unset for A and B but set for C
>> 2) A < B (due to early ira_reg_class_max_nregs comparison)
>> 3) B < C (due to following regno_assign_info comparison)
>>
>> It may then easily happen that A > C (due to regno_assign_info
>> comparison) which violates the transitiveness requirement of total
>> ordering.
>>
>> Unfortunately I'm not sure how to properly fix this so Cc-ing Vladimir
>> for help.
>>
>    Yury, thanks for reporting this.  Yes that could be a problem but I
> can not approve this patch as it might result in *significant*
> performance degradation.  I remember the code.  What you propose is the
> original patch (PR57878) and it was exactly modified to the current
> version because of the negative performance impact.  The current code is
> safe although it might result into infinite cycling for some sort
> algorithms but not for used qsort.
>
>    I'll think how to fix it better. Probably I will need two comparison
> functions for different assignment iterations.  The solution will need
> benchmarking as the code is critical for LRA performance.  Could you
> fill a bug report in order not to forget the issue.

Thanks! Submitted https://gcc.gnu.org/bugzilla/show_bug.cgi?id=68988

[PATCH 4/5] Fix intransitive comparison in compare_access_positions

[Yury Gribov]

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

Another intransitive comparison in reload_pseudo_compare_func. Buggy 
scenario:
1) A and B are ints of equal presion so we return 0
2) C is REAL and thus can compare differently to A and B

Cc-ing Martin who's the original author.

/Yury

[-- Attachment #2: 0004-Fix-intransitive-comparison-in-compare_access_positi.patch --]
[-- Type: text/x-patch, Size: 2827 bytes --]

From 6f3930ad81945f6b5d7aecfdda16089547a592d3 Mon Sep 17 00:00:00 2001
From: Yury Gribov <tetra2005@gmail.com>
Date: Sat, 12 Dec 2015 10:39:15 +0300
Subject: [PATCH 4/5] Fix intransitive comparison in compare_access_positions.

2015-12-17  Yury Gribov  <tetra2005@gmail.com>

	* tree-sra.c (compare_access_positions):
	Make transitive.

Error message:
Dec 10 23:51:43 yugr-ubuntu1404 : f951[31364]: qsort: comparison function is not transitive (comparison function 0x9aa8e0 (/home/yugr/build/gcc-4.9.3-patched-bootstrap/gcc/f951+5aa8e0), called from 0x9afeda (/home/yugr/build/gcc-4.9.3-patched-bootstrap/gcc/f951+5afeda), cmdline is "/home/yugr/build/gcc-4.9.3-patched-bootstrap/gcc/testsuite/gfortran/../../f951 /home/yugr/src/gcc-4.9.3-patched/gcc/testsuite/gfortran.fortran-torture/execute/intrinsic_set_exponent.f90 -quiet -dumpbase intrinsic_set_exponent.f90 -mtune=generic -march=x86-64 -auxbase intrinsic_set_exponent -O1 -w -fno-diagnostics-show-caret -fdiagnostics-color=never -fintrinsic-modules-path /home/yugr/install/gcc-4.9.3/lib/gcc/x86_64-unknown-linux-gnu/4.9.3/finclude -o /tmp/ccwhVAn9.s")
---
 gcc/tree-sra.c | 20 +++++++++++++-------
 1 file changed, 13 insertions(+), 7 deletions(-)

diff --git a/gcc/tree-sra.c b/gcc/tree-sra.c
index c4fea5b..5028850 100644
--- a/gcc/tree-sra.c
+++ b/gcc/tree-sra.c
@@ -1432,6 +1432,13 @@ scan_function (void)
   return ret;
 }
 
+static int
+imprecise_int_type_p (const tree type)
+{
+  return INTEGRAL_TYPE_P (type)
+    && (TREE_INT_CST_LOW (TYPE_SIZE (type)) != TYPE_PRECISION (type));
+}
+
 /* Helper of QSORT function. There are pointers to accesses in the array.  An
    access is considered smaller than another if it has smaller offset or if the
    offsets are the same but is size is bigger. */
@@ -1471,16 +1478,15 @@ compare_access_positions (const void *a, const void *b)
 	return -1;
       /* Put the integral type with the bigger precision first.  */
       else if (INTEGRAL_TYPE_P (f1->type)
-	       && INTEGRAL_TYPE_P (f2->type))
+	       && INTEGRAL_TYPE_P (f2->type)
+	       && TYPE_PRECISION (f2->type) != TYPE_PRECISION (f1->type))
 	return TYPE_PRECISION (f2->type) - TYPE_PRECISION (f1->type);
       /* Put any integral type with non-full precision last.  */
-      else if (INTEGRAL_TYPE_P (f1->type)
-	       && (TREE_INT_CST_LOW (TYPE_SIZE (f1->type))
-		   != TYPE_PRECISION (f1->type)))
+      else if (imprecise_int_type_p (f1->type)
+	       && !imprecise_int_type_p (f2->type))
 	return 1;
-      else if (INTEGRAL_TYPE_P (f2->type)
-	       && (TREE_INT_CST_LOW (TYPE_SIZE (f2->type))
-		   != TYPE_PRECISION (f2->type)))
+      else if (!imprecise_int_type_p (f1->type)
+	       && imprecise_int_type_p (f2->type))
 	return -1;
       /* Stabilize the sort.  */
       return TYPE_UID (f1->type) - TYPE_UID (f2->type);
-- 
1.9.1

Re: [PATCH 4/5] Fix intransitive comparison in compare_access_positions

[Martin Jambor]

Hi,

On Thu, Dec 17, 2015 at 12:02:11PM +0300, Yury Gribov wrote:
> Another intransitive comparison in reload_pseudo_compare_func. Buggy
> scenario:
> 1) A and B are ints of equal presion so we return 0
> 2) C is REAL and thus can compare differently to A and B
> 
> Cc-ing Martin who's the original author.

I cannot approve it but I also do not object to this change.
Thanks,

Martin

> 
> /Yury

> From 6f3930ad81945f6b5d7aecfdda16089547a592d3 Mon Sep 17 00:00:00 2001
> From: Yury Gribov <tetra2005@gmail.com>
> Date: Sat, 12 Dec 2015 10:39:15 +0300
> Subject: [PATCH 4/5] Fix intransitive comparison in compare_access_positions.
> 
> 2015-12-17  Yury Gribov  <tetra2005@gmail.com>
> 
> 	* tree-sra.c (compare_access_positions):
> 	Make transitive.
> 

[PATCH 5/5] Fix intransitive comparison in dr_group_sort_cmp

[Yury Gribov]

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

That's an interesting one. The original comparison function assumes that
operand_equal_p(a,b) is true iff compare_tree(a, b) == 0.
Unfortunately that's not true (functions are written by different authors).

This causes subtle violation of transitiveness.

I believe removing operand_equal_p should preserve the intended semantics
(same approach taken in another comparison function in this file - 
comp_dr_with_seg_len_pair).

Cc-ing Cong Hou and Richard who are the authours.

/Yury

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: 0005-Fix-intransitive-comparison-in-dr_group_sort_cmp.patch --]
[-- Type: text/x-patch; name="0005-Fix-intransitive-comparison-in-dr_group_sort_cmp.patch", Size: 3999 bytes --]

From 7fb1fd8b2027a3a3e2d914f8bd000fe53bffe110 Mon Sep 17 00:00:00 2001
From: Yury Gribov <tetra2005@gmail.com>
Date: Sun, 13 Dec 2015 01:30:22 +0300
Subject: [PATCH 5/5] Fix intransitive comparison in dr_group_sort_cmp.

2012-12-17  Yury Gribov  <tetra2005@gmail.com>

	* tree-vect-data-refs.c (dr_group_sort_cmp):
	Make transitive.

Error message:
Dec 10 22:28:59 yugr-ubuntu1404 : cc1plus[23983]: qsort: comparison function is not transitive (comparison function 0xddbbf0 (/home/yugr/build/gcc-4.9.3-patched-bootstrap/gcc/cc1plus+9dbbf0), called from 0xddd233 (/home/yugr/build/gcc-4.9.3-patched-bootstrap/gcc/cc1plus+9dd233), cmdline is "/home/yugr/build/gcc-4.9.3-patched-bootstrap/gcc/testsuite/g++/../../cc1plus -quiet -nostdinc++ -I /home/yugr/build/gcc-4.9.3-patched-bootstrap/x86_64-unknown-linux-gnu/libstdc++-v3/include/x86_64-unknown-linux-gnu -I /home/yugr/build/gcc-4.9.3-patched-bootstrap/x86_64-unknown-linux-gnu/libstdc++-v3/include -I /home/yugr/src/gcc-4.9.3-patched/libstdc++-v3/libsupc++ -I /home/yugr/src/gcc-4.9.3-patched/libstdc++-v3/include/backward -I /home/yugr/src/gcc-4.9.3-patched/libstdc++-v3/testsuite/util -imultiarch x86_64-linux-gnu -iprefix /home/yugr/install/gcc-4.9.3/lib/gcc/x86_64-unknown-linux-gnu/4.9.3/ -isystem /home/yugr/build/gcc-4.9.3-patched-bootstrap/gcc/testsuite/g++/../../include -isystem /home/yugr/build/gcc-4.9.3-patched-bootstrap/gcc/testsuite/g++/../../include-fixed -D_GNU_SOURCE /home/yugr/src/gcc-4.9.3-patched/gcc/testsuite/g++.dg/vect/pr43771.cc -quiet -dumpbase pr43771.cc -msse2 -mtune=generic -march=x86-64 -auxbase-strip pr43771.s -O2 -std=c++1y -fno-diagnostics-show-caret -fdiagnostics-color=never -fmessage-length=0 -ftree-vectorize -fvect-cost-model=unlimited -fdump-tree-vect-details -o pr43771.s")
---
 gcc/tree-vect-data-refs.c | 39 +++++++++++++--------------------------
 1 file changed, 13 insertions(+), 26 deletions(-)

diff --git a/gcc/tree-vect-data-refs.c b/gcc/tree-vect-data-refs.c
index 7755aaa..e69875a 100644
--- a/gcc/tree-vect-data-refs.c
+++ b/gcc/tree-vect-data-refs.c
@@ -2604,42 +2604,29 @@ dr_group_sort_cmp (const void *dra_, const void *drb_)
     return loopa->num < loopb->num ? -1 : 1;
 
   /* Ordering of DRs according to base.  */
-  if (!operand_equal_p (DR_BASE_ADDRESS (dra), DR_BASE_ADDRESS (drb), 0))
-    {
-      cmp = compare_tree (DR_BASE_ADDRESS (dra), DR_BASE_ADDRESS (drb));
-      if (cmp != 0)
-        return cmp;
-    }
+  cmp = compare_tree (DR_BASE_ADDRESS (dra), DR_BASE_ADDRESS (drb));
+  if (cmp != 0)
+    return cmp;
 
   /* And according to DR_OFFSET.  */
-  if (!dr_equal_offsets_p (dra, drb))
-    {
-      cmp = compare_tree (DR_OFFSET (dra), DR_OFFSET (drb));
-      if (cmp != 0)
-        return cmp;
-    }
+  cmp = compare_tree (DR_OFFSET (dra), DR_OFFSET (drb));
+  if (cmp != 0)
+    return cmp;
 
   /* Put reads before writes.  */
   if (DR_IS_READ (dra) != DR_IS_READ (drb))
     return DR_IS_READ (dra) ? -1 : 1;
 
   /* Then sort after access size.  */
-  if (!operand_equal_p (TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dra))),
-			TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (drb))), 0))
-    {
-      cmp = compare_tree (TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dra))),
-                          TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (drb))));
-      if (cmp != 0)
-        return cmp;
-    }
+  cmp = compare_tree (TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dra))),
+                      TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (drb))));
+  if (cmp != 0)
+    return cmp;
 
   /* And after step.  */
-  if (!operand_equal_p (DR_STEP (dra), DR_STEP (drb), 0))
-    {
-      cmp = compare_tree (DR_STEP (dra), DR_STEP (drb));
-      if (cmp != 0)
-        return cmp;
-    }
+  cmp = compare_tree (DR_STEP (dra), DR_STEP (drb));
+  if (cmp != 0)
+    return cmp;
 
   /* Then sort after DR_INIT.  In case of identical DRs sort after stmt UID.  */
   cmp = tree_int_cst_compare (DR_INIT (dra), DR_INIT (drb));
-- 
1.9.1

Re: [PATCH 5/5] Fix intransitive comparison in dr_group_sort_cmp

[Richard Biener]

On Thu, 17 Dec 2015, Yury Gribov wrote:

> That's an interesting one. The original comparison function assumes that
> operand_equal_p(a,b) is true iff compare_tree(a, b) == 0.
> Unfortunately that's not true (functions are written by different authors).
> 
> This causes subtle violation of transitiveness.
> 
> I believe removing operand_equal_p should preserve the intended semantics
> (same approach taken in another comparison function in this file -
> comp_dr_with_seg_len_pair).
> 
> Cc-ing Cong Hou and Richard who are the authours.

I don't think the patch is good.  compare_tree really doesn't expect
equal elements (and it returning zero is bad or a bug).  But it's also
"lazy" in that it will return 0 when it hopes a further disambiguation
inside dr_group_sort_cmp on a different field will eventually lead to
a non-zero compare_tree.

So eventually if compare_tree returns zero we have to fall back to the
final disambiguator using gimple_uid.

That said, I'd like to see the testcase where you observe an
intransitive comparison.

Richard.

Re: [PATCH 5/5] Fix intransitive comparison in dr_group_sort_cmp

[Yury Gribov]

On 12/17/2015 02:57 PM, Richard Biener wrote:
> On Thu, 17 Dec 2015, Yury Gribov wrote:
>
>> That's an interesting one. The original comparison function assumes that
>> operand_equal_p(a,b) is true iff compare_tree(a, b) == 0.
>> Unfortunately that's not true (functions are written by different authors).
>>
>> This causes subtle violation of transitiveness.
>>
>> I believe removing operand_equal_p should preserve the intended semantics
>> (same approach taken in another comparison function in this file -
>> comp_dr_with_seg_len_pair).
>>
>> Cc-ing Cong Hou and Richard who are the authours.
>
> I don't think the patch is good.  compare_tree really doesn't expect
> equal elements (and it returning zero is bad or a bug).

Hm but that's how it's used in other comparator in this file 
(comp_dr_with_seg_len_pair).

> But it's also
> "lazy" in that it will return 0 when it hopes a further disambiguation
> inside dr_group_sort_cmp on a different field will eventually lead to
> a non-zero compare_tree.
>
> So eventually if compare_tree returns zero we have to fall back to the
> final disambiguator using gimple_uid.
 >
> That said, I'd like to see the testcase where you observe an
> intransitive comparison.

Let me dig my debugging logs (I'll send detailed repro tomorrow).

/Yura

Re: [PATCH 5/5] Fix intransitive comparison in dr_group_sort_cmp

[Richard Biener]

On Thu, 17 Dec 2015, Yury Gribov wrote:

> On 12/17/2015 02:57 PM, Richard Biener wrote:
> > On Thu, 17 Dec 2015, Yury Gribov wrote:
> > 
> > > That's an interesting one. The original comparison function assumes that
> > > operand_equal_p(a,b) is true iff compare_tree(a, b) == 0.
> > > Unfortunately that's not true (functions are written by different
> > > authors).
> > > 
> > > This causes subtle violation of transitiveness.
> > > 
> > > I believe removing operand_equal_p should preserve the intended semantics
> > > (same approach taken in another comparison function in this file -
> > > comp_dr_with_seg_len_pair).
> > > 
> > > Cc-ing Cong Hou and Richard who are the authours.
> > 
> > I don't think the patch is good.  compare_tree really doesn't expect
> > equal elements (and it returning zero is bad or a bug).
> 
> Hm but that's how it's used in other comparator in this file
> (comp_dr_with_seg_len_pair).

But for sure

  switch (code)
    {
    /* For const values, we can just use hash values for comparisons.  */
    case INTEGER_CST:
    case REAL_CST:
    case FIXED_CST:
    case STRING_CST:
    case COMPLEX_CST:
    case VECTOR_CST:
      {
        hashval_t h1 = iterative_hash_expr (t1, 0);
        hashval_t h2 = iterative_hash_expr (t2, 0);
        if (h1 != h2)
          return h1 < h2 ? -1 : 1;
        break;
      }

doesn't detect un-equality correctly (it assumes the hash is 
collision-free).

Also note that operator== of dr_with_seg_len again also uses
operand_equal_p (plus compare_tree).

IMHO compare_tree should be cleaned up with respect to what
trees we expect here (no REAL_CSTs for example) and properly
do comparisons.

> > But it's also
> > "lazy" in that it will return 0 when it hopes a further disambiguation
> > inside dr_group_sort_cmp on a different field will eventually lead to
> > a non-zero compare_tree.
> > 
> > So eventually if compare_tree returns zero we have to fall back to the
> > final disambiguator using gimple_uid.
> >
> > That said, I'd like to see the testcase where you observe an
> > intransitive comparison.
> 
> Let me dig my debugging logs (I'll send detailed repro tomorrow).

Thanks.

Richard.

Re: [PATCH 5/5] Fix intransitive comparison in dr_group_sort_cmp

[Yury Gribov]

On 12/17/2015 03:51 PM, Richard Biener wrote:
> On Thu, 17 Dec 2015, Yury Gribov wrote:
>
>> On 12/17/2015 02:57 PM, Richard Biener wrote:
>>> On Thu, 17 Dec 2015, Yury Gribov wrote:
>>>
>>>> That's an interesting one. The original comparison function assumes that
>>>> operand_equal_p(a,b) is true iff compare_tree(a, b) == 0.
>>>> Unfortunately that's not true (functions are written by different
>>>> authors).
>>>>
>>>> This causes subtle violation of transitiveness.
>>>>
>>>> I believe removing operand_equal_p should preserve the intended semantics
>>>> (same approach taken in another comparison function in this file -
>>>> comp_dr_with_seg_len_pair).
>>>>
>>>> Cc-ing Cong Hou and Richard who are the authours.
>>>
>>> I don't think the patch is good.  compare_tree really doesn't expect
>>> equal elements (and it returning zero is bad or a bug).
>>
>> Hm but that's how it's used in other comparator in this file
>> (comp_dr_with_seg_len_pair).
>
> But for sure
>
>    switch (code)
>      {
>      /* For const values, we can just use hash values for comparisons.  */
>      case INTEGER_CST:
>      case REAL_CST:
>      case FIXED_CST:
>      case STRING_CST:
>      case COMPLEX_CST:
>      case VECTOR_CST:
>        {
>          hashval_t h1 = iterative_hash_expr (t1, 0);
>          hashval_t h2 = iterative_hash_expr (t2, 0);
>          if (h1 != h2)
>            return h1 < h2 ? -1 : 1;
>          break;
>        }
>
> doesn't detect un-equality correctly (it assumes the hash is
> collision-free).
>
> Also note that operator== of dr_with_seg_len again also uses
> operand_equal_p (plus compare_tree).
>
> IMHO compare_tree should be cleaned up with respect to what
> trees we expect here (no REAL_CSTs for example) and properly
> do comparisons.
>
>>> But it's also
>>> "lazy" in that it will return 0 when it hopes a further disambiguation
>>> inside dr_group_sort_cmp on a different field will eventually lead to
>>> a non-zero compare_tree.
>>>
>>> So eventually if compare_tree returns zero we have to fall back to the
>>> final disambiguator using gimple_uid.
>>>
>>> That said, I'd like to see the testcase where you observe an
>>> intransitive comparison.
>>
>> Let me dig my debugging logs (I'll send detailed repro tomorrow).

Added home address.

Re: [PATCH 5/5] Fix intransitive comparison in dr_group_sort_cmp

[Yuri Gribov]

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

On Fri, Dec 18, 2015 at 11:20 PM, Yury Gribov <y.gribov@samsung.com> wrote:
> On 12/17/2015 03:51 PM, Richard Biener wrote:
>>
>> On Thu, 17 Dec 2015, Yury Gribov wrote:
>>
>>> On 12/17/2015 02:57 PM, Richard Biener wrote:
>>>>
>>>> On Thu, 17 Dec 2015, Yury Gribov wrote:
>>>>
>>>>> That's an interesting one. The original comparison function assumes
>>>>> that
>>>>> operand_equal_p(a,b) is true iff compare_tree(a, b) == 0.
>>>>> Unfortunately that's not true (functions are written by different
>>>>> authors).
>>>>>
>>>>> This causes subtle violation of transitiveness.
>>>>>
>>>>> I believe removing operand_equal_p should preserve the intended
>>>>> semantics
>>>>> (same approach taken in another comparison function in this file -
>>>>> comp_dr_with_seg_len_pair).
>>>>>
>>>>> Cc-ing Cong Hou and Richard who are the authours.
>>>>
>>>>
>>>> I don't think the patch is good.  compare_tree really doesn't expect
>>>> equal elements (and it returning zero is bad or a bug).
>>>
>>>
>>> Hm but that's how it's used in other comparator in this file
>>> (comp_dr_with_seg_len_pair).
>>
>>
>> But for sure
>>
>>    switch (code)
>>      {
>>      /* For const values, we can just use hash values for comparisons.  */
>>      case INTEGER_CST:
>>      case REAL_CST:
>>      case FIXED_CST:
>>      case STRING_CST:
>>      case COMPLEX_CST:
>>      case VECTOR_CST:
>>        {
>>          hashval_t h1 = iterative_hash_expr (t1, 0);
>>          hashval_t h2 = iterative_hash_expr (t2, 0);
>>          if (h1 != h2)
>>            return h1 < h2 ? -1 : 1;
>>          break;
>>        }
>>
>> doesn't detect un-equality correctly (it assumes the hash is
>> collision-free).
>>
>> Also note that operator== of dr_with_seg_len again also uses
>> operand_equal_p (plus compare_tree).
>>
>> IMHO compare_tree should be cleaned up with respect to what
>> trees we expect here (no REAL_CSTs for example) and properly
>> do comparisons.
>>
>>>> But it's also
>>>> "lazy" in that it will return 0 when it hopes a further disambiguation
>>>> inside dr_group_sort_cmp on a different field will eventually lead to
>>>> a non-zero compare_tree.
>>>>
>>>> So eventually if compare_tree returns zero we have to fall back to the
>>>> final disambiguator using gimple_uid.
>>>>
>>>> That said, I'd like to see the testcase where you observe an
>>>> intransitive comparison.
>>>
>>>
>>> Let me dig my debugging logs (I'll send detailed repro tomorrow).
>
> Added home address.

Richard,

I was doing my original testing on an older GCC (actually 4.9) and it
seems that this particular issue does not reproduce on current trunk.
But from what I can see the problem is still in the code which I'll
now try to explain.

Here's the problem that was detected by the tool:

(gdb) p dr_group_sort_cmp($dr1,$dr2)
$1 = -1
(gdb) p dr_group_sort_cmp($dr2,$dr3)
$2 = -1
(gdb) p dr_group_sort_cmp($dr1,$dr3)
$3 = 1

In other words, dr1 < dr2 and dr2 < dr3 but dr1 > dr3 (which is a
violation of transitivity axiom and will generally drive qsort mad).
Let's see why that happens.

Comparison starts at base addresses which are

(gdb) cal debug_generic_expr($ba1)
b_7(D) + (sizetype) i_69 * 4
(gdb) cal debug_generic_expr($ba2)
a_12(D) + (sizetype) ((long unsigned int) i_69 * 4)
(gdb) cal debug_generic_expr($ba3)
b_7(D) + (sizetype) ((long unsigned int) i_69 * 4)

Now here are results for operand_equals_p:

(gdb) cal operand_equal_p($ba1,$ba2,0)
$1 = 0
(gdb) cal operand_equal_p($ba2,$ba3,0)
$3 = 0

This means that to compare dr1 vs. dr2 and dr2 vs. dr3 we use compare_tree:

(gdb) cal compare_tree($ba1,$ba2)
$4 = -1
(gdb) cal compare_tree($ba2,$ba3)
$5 = -1

For dr1 vs. dr3 situation is more interesting. We continue with other checks
in dr_group_sort_cmp. Everything is equal:

(gdb) p dr_equal_offsets_p(*$dr1,*$dr3)
$7 = true
(gdb) p $dr1.is_read
$9 = false
(gdb) p $dr3.is_read
$11 = false
(gdb) cal operand_equal_p($dr1.ref.typed.type.type_common.size_unit,$dr3.ref.typed.type.type_common.size_unit,0)
$15 = 1
(gdb) cal operand_equal_p($dr1.innermost.step,$dr3.innermost.step,0)
$16 = 1

Until the very end where we compare initial values:

(gdb) cal tree_int_cst_compare($dr1.innermost.init,$dr3.innermost.init,0)
$18 = 1

I think the core reason is probably that pattern that's used here i.e.
  if(P(x,y))
    return cmp1(x,y);
  return cmp2(x,y);
will in general not be a valid total ordering even if cmp1 or cmp2 are.
(In our case P = operand_equals_p, cmp1 = compare_tree, cmp2 =
tree_int_cst_compare).

FTR I compiled the attached repro with 4.9.3 like this:
$ ./cc1plus -quiet -O2 -ftree-vectorize repro.i

/Yura

[-- Attachment #2: repro.i --]
[-- Type: text/plain, Size: 110 bytes --]

void foo (int n, int *a, int *b)
{
   int i;
   for (i = 0; i < n; i += 2)
       b[i] = b[i+1] = a[i] + 1;
}

Re: [PATCH 5/5] Fix intransitive comparison in dr_group_sort_cmp

[Yury Gribov]

On 12/19/2015 01:30 AM, Yuri Gribov wrote:
> On Fri, Dec 18, 2015 at 11:20 PM, Yury Gribov <y.gribov@samsung.com> wrote:
>> On 12/17/2015 03:51 PM, Richard Biener wrote:
>>>
>>> On Thu, 17 Dec 2015, Yury Gribov wrote:
>>>
>>>> On 12/17/2015 02:57 PM, Richard Biener wrote:
>>>>>
>>>>> On Thu, 17 Dec 2015, Yury Gribov wrote:
>>>>>
>>>>>> That's an interesting one. The original comparison function assumes
>>>>>> that
>>>>>> operand_equal_p(a,b) is true iff compare_tree(a, b) == 0.
>>>>>> Unfortunately that's not true (functions are written by different
>>>>>> authors).
>>>>>>
>>>>>> This causes subtle violation of transitiveness.
>>>>>>
>>>>>> I believe removing operand_equal_p should preserve the intended
>>>>>> semantics
>>>>>> (same approach taken in another comparison function in this file -
>>>>>> comp_dr_with_seg_len_pair).
>>>>>>
>>>>>> Cc-ing Cong Hou and Richard who are the authours.
>>>>>
>>>>>
>>>>> I don't think the patch is good.  compare_tree really doesn't expect
>>>>> equal elements (and it returning zero is bad or a bug).
>>>>
>>>>
>>>> Hm but that's how it's used in other comparator in this file
>>>> (comp_dr_with_seg_len_pair).
>>>
>>>
>>> But for sure
>>>
>>>     switch (code)
>>>       {
>>>       /* For const values, we can just use hash values for comparisons.  */
>>>       case INTEGER_CST:
>>>       case REAL_CST:
>>>       case FIXED_CST:
>>>       case STRING_CST:
>>>       case COMPLEX_CST:
>>>       case VECTOR_CST:
>>>         {
>>>           hashval_t h1 = iterative_hash_expr (t1, 0);
>>>           hashval_t h2 = iterative_hash_expr (t2, 0);
>>>           if (h1 != h2)
>>>             return h1 < h2 ? -1 : 1;
>>>           break;
>>>         }
>>>
>>> doesn't detect un-equality correctly (it assumes the hash is
>>> collision-free).
>>>
>>> Also note that operator== of dr_with_seg_len again also uses
>>> operand_equal_p (plus compare_tree).
>>>
>>> IMHO compare_tree should be cleaned up with respect to what
>>> trees we expect here (no REAL_CSTs for example) and properly
>>> do comparisons.
>>>
>>>>> But it's also
>>>>> "lazy" in that it will return 0 when it hopes a further disambiguation
>>>>> inside dr_group_sort_cmp on a different field will eventually lead to
>>>>> a non-zero compare_tree.
>>>>>
>>>>> So eventually if compare_tree returns zero we have to fall back to the
>>>>> final disambiguator using gimple_uid.
>>>>>
>>>>> That said, I'd like to see the testcase where you observe an
>>>>> intransitive comparison.
>>>>
>>>>
>>>> Let me dig my debugging logs (I'll send detailed repro tomorrow).
>>
>> Added home address.
>
> Richard,
>
> I was doing my original testing on an older GCC (actually 4.9) and it
> seems that this particular issue does not reproduce on current trunk.
> But from what I can see the problem is still in the code which I'll
> now try to explain.
>
> Here's the problem that was detected by the tool:
>
> (gdb) p dr_group_sort_cmp($dr1,$dr2)
> $1 = -1
> (gdb) p dr_group_sort_cmp($dr2,$dr3)
> $2 = -1
> (gdb) p dr_group_sort_cmp($dr1,$dr3)
> $3 = 1
>
> In other words, dr1 < dr2 and dr2 < dr3 but dr1 > dr3 (which is a
> violation of transitivity axiom and will generally drive qsort mad).
> Let's see why that happens.
>
> Comparison starts at base addresses which are
>
> (gdb) cal debug_generic_expr($ba1)
> b_7(D) + (sizetype) i_69 * 4
> (gdb) cal debug_generic_expr($ba2)
> a_12(D) + (sizetype) ((long unsigned int) i_69 * 4)
> (gdb) cal debug_generic_expr($ba3)
> b_7(D) + (sizetype) ((long unsigned int) i_69 * 4)
>
> Now here are results for operand_equals_p:
>
> (gdb) cal operand_equal_p($ba1,$ba2,0)
> $1 = 0
> (gdb) cal operand_equal_p($ba2,$ba3,0)
> $3 = 0
>
> This means that to compare dr1 vs. dr2 and dr2 vs. dr3 we use compare_tree:
>
> (gdb) cal compare_tree($ba1,$ba2)
> $4 = -1
> (gdb) cal compare_tree($ba2,$ba3)
> $5 = -1
>
> For dr1 vs. dr3 situation is more interesting. We continue with other checks
> in dr_group_sort_cmp. Everything is equal:
>
> (gdb) p dr_equal_offsets_p(*$dr1,*$dr3)
> $7 = true
> (gdb) p $dr1.is_read
> $9 = false
> (gdb) p $dr3.is_read
> $11 = false
> (gdb) cal operand_equal_p($dr1.ref.typed.type.type_common.size_unit,$dr3.ref.typed.type.type_common.size_unit,0)
> $15 = 1
> (gdb) cal operand_equal_p($dr1.innermost.step,$dr3.innermost.step,0)
> $16 = 1
>
> Until the very end where we compare initial values:
>
> (gdb) cal tree_int_cst_compare($dr1.innermost.init,$dr3.innermost.init,0)
> $18 = 1
>
> I think the core reason is probably that pattern that's used here i.e.
>    if(P(x,y))
>      return cmp1(x,y);
>    return cmp2(x,y);
> will in general not be a valid total ordering even if cmp1 or cmp2 are.
> (In our case P = operand_equals_p, cmp1 = compare_tree, cmp2 =
> tree_int_cst_compare).
>
> FTR I compiled the attached repro with 4.9.3 like this:
> $ ./cc1plus -quiet -O2 -ftree-vectorize repro.i

Richard,

What's your call on this? Do you want a GCC6-relevant repro?

/Yura

Re: [PATCH 5/5] Fix intransitive comparison in dr_group_sort_cmp

[Richard Biener]

On Sat, 19 Dec 2015, Yuri Gribov wrote:

> On Fri, Dec 18, 2015 at 11:20 PM, Yury Gribov <y.gribov@samsung.com> wrote:
> > On 12/17/2015 03:51 PM, Richard Biener wrote:
> >>
> >> On Thu, 17 Dec 2015, Yury Gribov wrote:
> >>
> >>> On 12/17/2015 02:57 PM, Richard Biener wrote:
> >>>>
> >>>> On Thu, 17 Dec 2015, Yury Gribov wrote:
> >>>>
> >>>>> That's an interesting one. The original comparison function assumes
> >>>>> that
> >>>>> operand_equal_p(a,b) is true iff compare_tree(a, b) == 0.
> >>>>> Unfortunately that's not true (functions are written by different
> >>>>> authors).
> >>>>>
> >>>>> This causes subtle violation of transitiveness.
> >>>>>
> >>>>> I believe removing operand_equal_p should preserve the intended
> >>>>> semantics
> >>>>> (same approach taken in another comparison function in this file -
> >>>>> comp_dr_with_seg_len_pair).
> >>>>>
> >>>>> Cc-ing Cong Hou and Richard who are the authours.
> >>>>
> >>>>
> >>>> I don't think the patch is good.  compare_tree really doesn't expect
> >>>> equal elements (and it returning zero is bad or a bug).
> >>>
> >>>
> >>> Hm but that's how it's used in other comparator in this file
> >>> (comp_dr_with_seg_len_pair).
> >>
> >>
> >> But for sure
> >>
> >>    switch (code)
> >>      {
> >>      /* For const values, we can just use hash values for comparisons.  */
> >>      case INTEGER_CST:
> >>      case REAL_CST:
> >>      case FIXED_CST:
> >>      case STRING_CST:
> >>      case COMPLEX_CST:
> >>      case VECTOR_CST:
> >>        {
> >>          hashval_t h1 = iterative_hash_expr (t1, 0);
> >>          hashval_t h2 = iterative_hash_expr (t2, 0);
> >>          if (h1 != h2)
> >>            return h1 < h2 ? -1 : 1;
> >>          break;
> >>        }
> >>
> >> doesn't detect un-equality correctly (it assumes the hash is
> >> collision-free).
> >>
> >> Also note that operator== of dr_with_seg_len again also uses
> >> operand_equal_p (plus compare_tree).
> >>
> >> IMHO compare_tree should be cleaned up with respect to what
> >> trees we expect here (no REAL_CSTs for example) and properly
> >> do comparisons.
> >>
> >>>> But it's also
> >>>> "lazy" in that it will return 0 when it hopes a further disambiguation
> >>>> inside dr_group_sort_cmp on a different field will eventually lead to
> >>>> a non-zero compare_tree.
> >>>>
> >>>> So eventually if compare_tree returns zero we have to fall back to the
> >>>> final disambiguator using gimple_uid.
> >>>>
> >>>> That said, I'd like to see the testcase where you observe an
> >>>> intransitive comparison.
> >>>
> >>>
> >>> Let me dig my debugging logs (I'll send detailed repro tomorrow).
> >
> > Added home address.
> 
> Richard,
> 
> I was doing my original testing on an older GCC (actually 4.9) and it
> seems that this particular issue does not reproduce on current trunk.
> But from what I can see the problem is still in the code which I'll
> now try to explain.
> 
> Here's the problem that was detected by the tool:
> 
> (gdb) p dr_group_sort_cmp($dr1,$dr2)
> $1 = -1
> (gdb) p dr_group_sort_cmp($dr2,$dr3)
> $2 = -1
> (gdb) p dr_group_sort_cmp($dr1,$dr3)
> $3 = 1
> 
> In other words, dr1 < dr2 and dr2 < dr3 but dr1 > dr3 (which is a
> violation of transitivity axiom and will generally drive qsort mad).
> Let's see why that happens.
> 
> Comparison starts at base addresses which are
> 
> (gdb) cal debug_generic_expr($ba1)
> b_7(D) + (sizetype) i_69 * 4
> (gdb) cal debug_generic_expr($ba2)
> a_12(D) + (sizetype) ((long unsigned int) i_69 * 4)
> (gdb) cal debug_generic_expr($ba3)
> b_7(D) + (sizetype) ((long unsigned int) i_69 * 4)
> 
> Now here are results for operand_equals_p:
> 
> (gdb) cal operand_equal_p($ba1,$ba2,0)
> $1 = 0
> (gdb) cal operand_equal_p($ba2,$ba3,0)
> $3 = 0
> 
> This means that to compare dr1 vs. dr2 and dr2 vs. dr3 we use compare_tree:
> 
> (gdb) cal compare_tree($ba1,$ba2)
> $4 = -1
> (gdb) cal compare_tree($ba2,$ba3)
> $5 = -1
> 
> For dr1 vs. dr3 situation is more interesting. We continue with other checks
> in dr_group_sort_cmp. Everything is equal:
> 
> (gdb) p dr_equal_offsets_p(*$dr1,*$dr3)
> $7 = true
> (gdb) p $dr1.is_read
> $9 = false
> (gdb) p $dr3.is_read
> $11 = false
> (gdb) cal operand_equal_p($dr1.ref.typed.type.type_common.size_unit,$dr3.ref.typed.type.type_common.size_unit,0)
> $15 = 1
> (gdb) cal operand_equal_p($dr1.innermost.step,$dr3.innermost.step,0)
> $16 = 1
> 
> Until the very end where we compare initial values:
> 
> (gdb) cal tree_int_cst_compare($dr1.innermost.init,$dr3.innermost.init,0)
> $18 = 1
> 
> I think the core reason is probably that pattern that's used here i.e.
>   if(P(x,y))
>     return cmp1(x,y);
>   return cmp2(x,y);
> will in general not be a valid total ordering even if cmp1 or cmp2 are.
> (In our case P = operand_equals_p, cmp1 = compare_tree, cmp2 =
> tree_int_cst_compare).

Yeah, I agree with that.  But I don't agree with your simple fix.

Can you please file a bugreport about this issue so we can track it
and work on it for GCC 7?

I believe that compare_tree needs to handle the equality case "properly".

Thanks,
Richard.