https://gcc.gnu.org/bugzilla/show_bug.cgi?id=82397
Richard Biener <rguenth at gcc dot gnu.org> changed:
What |Removed |Added
----------------------------------------------------------------------------
Keywords| |ice-checking
Status|UNCONFIRMED |NEW
Last reconfirmed| |2017-10-04
Version|unknown |8.0
Target Milestone|--- |8.0
Summary|qsort comparator |[8 Regression] qsort
|non-negative on sorted |comparator non-negative on
|output: 1 in |sorted output: 1 in
|vect_analyze_data_ref_acces |vect_analyze_data_ref_acces
|ses |ses
Ever confirmed|0 |1
--- Comment #2 from Richard Biener <rguenth at gcc dot gnu.org> ---
(In reply to Alexander Monakov from comment #1)
> This is because operand_equal_p is "smarter" than data_ref_compare_tree. We
> have something like
>
> A: (long)_1 + (_2 + _3)
> B: (_2 + _4) + (long)_1
> C: (_2 + _3) + (long)_1
>
> with A == C != B according to operand_equal_p (and A < B < C according to
> data_ref_compare_tree), making comparison steps like this non-transitive:
>
> if (!operand_equal_p (DR_BASE_ADDRESS (dra), DR_BASE_ADDRESS (drb), 0))
> {
> cmp = data_ref_compare_tree (DR_BASE_ADDRESS (dra),
> DR_BASE_ADDRESS (drb));
>
>
> Perhaps additive chains in compared operands should be canonicalized first
> so that if two items are equal according to operand_equal_p they're also
> guaranteed to be equal according to data_ref_compare_tree?
Possibly. operand_equal_p does the following which is exponential.
case tcc_comparison:
case tcc_binary:
if (OP_SAME (0) && OP_SAME (1))
return 1;
/* For commutative ops, allow the other order. */
return (commutative_tree_code (TREE_CODE (arg0))
&& operand_equal_p (TREE_OPERAND (arg0, 0),
TREE_OPERAND (arg1, 1), flags)
&& operand_equal_p (TREE_OPERAND (arg0, 1),
TREE_OPERAND (arg1, 0), flags));
I think sth better would be
if (commutative_tree_code (...)
&& tree_swap_operands ())
std::swap (...);
and just compare once. tree-swap-operands doesn't handle enough cases so
we'd lose some equalities. But exponential behavior is bad.
