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

[Richard Biener <rguenther at suse dot de>]

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.