[PATCH 5/5] Fix intransitive comparison in dr_group_sort_cmp

[Yuri Gribov]

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
-------------- next part --------------
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;
}