On 12/19/2015 01:30 AM, Yuri Gribov wrote:
On Fri, Dec 18, 2015 at 11:20 PM, Yury Gribov <y.gri...@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
