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

[Yury Gribov <y.gribov@samsung.com>]

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