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

[Richard Biener <rguenther at suse dot de>]

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.