[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.